문제 푼 날짜 : 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;
}
}
};
그렇게 좋은 풀이는 아닌 것 같은데, 좀 더 빠르게 구현할 수 있는지 고민해보고 다시 풀어봐야겠다.