首页 > 代码库 > leetcode -- Implement strStr()
leetcode -- Implement strStr()
反正总是有人要赢，那为什么不能是我呢~
[问题描述]
Implement strStr().
Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.
[解题思路]
1.KMP. 2.暴力
1 char *Solution::strStr(char* haystack, char* needle) 2 { 3 if (haystack == NULL || needle == NULL) 4 return NULL; 5 if (needle[0] == ‘\0‘) 6 return haystack; 7 int next[strlen(needle)];//计算nextval 8 int i = 0, j = -1; 9 next[i] = -1;10 while (needle[i] != ‘\0‘){11 if (j == -1 || needle[i] == needle[j]){12 i++, j++; next[i] = j;13 }14 else{15 j = next[j];16 }17 }18 i = 0, j = 0;//匹配字符串19 char* ans = NULL;20 while (haystack[i] != ‘\0‘){21 while (j >= 0 && haystack[i] != needle[j])22 j = next[j];23 i++; j++;24 if (needle[j] == ‘\0‘){25 ans = haystack + i - j;26 return ans;27 }28 }29 return ans;30 }
暴力有效的方法1：
1 char *strStr(char *haystack, char *needle) 2 { 3 if(needle == NULL) return haystack; 4 else{ 5 int len1 =strlen(haystack),len2 = strlen(needle); 6 if(len2 == 0) return haystack; 7 for(int i = 0 ; i < len1-len2+1; ++ i){ 8 if(strncmp(haystack+i,needle,len2) == 0) return haystack+i; 9 }10 return NULL;11 }12 }
暴力有效的方法2：
1 char *strStr(char *haystack, char *needle) 2 { 3 int i,j; 4 for (i = j = 0; haystack[i] && needle[j];) { 5 if (haystack[i] == needle[j]) { 6 ++i; 7 ++j; 8 } else { 9 i = i - j + 1; 10 j = 0; 11 } 12 } 13 return needle[j] ? 0 : (haystack + i - j); 14 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。