Implement strStr().
Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.
-------------------------------------------------
KMP, O(n),
class Solution { public: vector<int> computePrefixTable(string pattern) { int m = pattern.length(); vector<int> table(m,0); int matchedLength = 0; for (int i = 1; i < m; i++) { // until find the next char at matchedLength is equal to char at i // or matchedLength is zero while (matchedLength > 0 && pattern[matchedLength] != pattern[i]) { matchedLength = table[matchedLength - 1]; } if (pattern[matchedLength] == pattern[i]) { matchedLength++; } table[i] = matchedLength; } return table; } int KMP(string source, string pattern) { int n = source.length(); int m = pattern.length(); vector<int> table = computePrefixTable(pattern); int matchedLength = 0; for (int i = 0; i < n; i++) { while (matchedLength > 0 && pattern[matchedLength] != source[i]) { matchedLength = table[matchedLength - 1]; } if (pattern[matchedLength] == source[i]) { matchedLength++; } if (matchedLength == m) { return i - m + 1; } } return -1; } int strStr(string haystack, string needle) { if (needle == "") return 0; if (haystack == "") return -1; return KMP(haystack,needle); } };Solution #2 O(m*n), improved brute force
class Solution { public: char *strStr(char *haystack, char *needle) { // IMPORTANT: Please reset any member data you declared, as // the same Solution instance will be reused for each test case. if (*needle == NULL) return haystack; if (!*haystack) return NULL; char* adv = haystack; char* temp = needle; while (*++temp) { adv++; } while (*adv != NULL) { char* itr1 = haystack; char* itr2 = needle; while (*itr1 && *itr2 && *itr1 == *itr2) { itr1++; itr2++; } if (!*itr2) return haystack; haystack++; adv++; } return NULL; } };
No comments:
Post a Comment