Implement strStr().
Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
C Solution 1:
int strStr(char* haystack, char* needle) {
if (!needle || !*needle) return 0;
char *p = needle;
int res = 0;
while (haystack[res]) {
if (*p == haystack[res]) {
char *q = haystack + res;
while (*++p && *p == *++q);
if (!*p) return res;
}
res++;
p = needle;
}
return -1;
}
C Solution 2:
int strStr(char* haystack, char* needle) {
if (!needle || !*needle) return 0;
int hlen = strlen(haystack);
int nlen = strlen(needle);
if (nlen > hlen) return -1;
char *p = needle;
int res = 0;
while (haystack[res] && res <= hlen - nlen) {
if (*p == haystack[res]) {
char *q = haystack + res;
while (*++p && *p == *++q);
if (!*p) return res;
}
res++;
p = needle;
}
return -1;
}
Summary:
- The runtime of solution 1 is 449ms, while that of solution 2 is 3ms.
LeetCode: 28. Implement strStr()
近期评论