[LeetCode] 28. Implement strStr()

김개발·2021년 11월 26일
0

LeetCode

목록 보기
6/10

문제 푼 날짜 : 2021-11-26

문제

문제 링크 : https://leetcode.com/problems/implement-strstr/

접근 및 풀이

O(n^2)으로 무난하게 풀 수 있는 문제였다.
처음엔 부분 문자열을 비교해줄 때 substr 함수를 이용하였는데, Memory Limit Exceeded가 뜨는 바람에 매 자릿수마다 비교해주었다.

코드

class Solution {
public:
    int strStr(string haystack, string needle) {
        int hLen = haystack.length();
        int nLen = needle.length();
        
        if (nLen == 0) {
            return 0;
        }
        
        char firstChar = needle[0];
        int i;
        for (i = 0; i < hLen; i++) {
            char ch = haystack[i];
            if (ch == firstChar) {
                bool flag = true;
                for (int j = 1; j < nLen; j++) {
                    if (haystack[i + j] != needle[j]) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    break;
                }
            } else {
                continue;
            }
        }
        if (i == hLen) {
            return -1;
        } else {
            return i;
        }
    }
};

결과

피드백

그렇게 좋은 풀이는 아닌 것 같은데, 좀 더 빠르게 구현할 수 있는지 고민해보고 다시 풀어봐야겠다.

profile
개발을 잘하고 싶은 사람

0개의 댓글