[C] LeetCode 28. Find the Index of the First Occurrence in a String

문제(원문)

문제(번역)

needle과 haystack 문자열 변수가 주어졌을 때, haystack 안에 needle 변수에 있는 문자열이 처음 나타나는 인덱스를 반환하라.

만약 존재하지 않는다면 -1을 반환하라.

접근 과정

단순하게 생각했다.

이중 반복문을 이용해 needle 문자열이 haystack 문자열 안에 있는지 매번 확인했다.

 

먼저 문자열의 길이를 측정해 h와 n에 각각 저장했다.

그리고 0 부터 h-n 까지 반복하면서 그 자리에서 n칸 앞으로 haystack에 needle 문자열이 있는지 확인했다.

소스코드

int strStr(char* haystack, char* needle) {
    int h = 0, n = 0, o = 0;
    while(haystack[h] != '\0') { h++;}
    while(needle[n] != '\0') {n++;}
    for(int i =0; i < h - n + 1; i++ ) {
        o = 0;
        for(int j=i; j<i+n; j++) {
            if(haystack[j] != needle[o]) {
                break;
            } else o++;
        }
        if(o == n) return i;
    }
    return -1;
}

 

haystack의 문자열 길이를 N, needle 문자열의 길이를 K라고 하자.

그럼 이 풀이의 시간복잡도는 O(NK)가 될 것이다.

 

 

생각보다 내 풀이는 메모리를 많이 잡아먹는다. 나보다 적은 메모리를 쓰는 사람들은 대체 어떻게 풀었을까?