admin管理员组文章数量:1636930
Implement strStr().
Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.
in Java, there is an API function name indexof(), it returns index within this string of the first occurrence of the specifiedsubstring.
java 实现
public String strStr(String haystack, String needle) {
if(haystack.length()<=0) return null;
int i = haystack.indexOf(needle);
if(i==-1) return null;
else{
return haystack.substring(i);
}
}
another solution:
public String strStr(String haystack, String needle) {
if(haystack.length()<=0 && needle.length()>0) return null;
for(int i=0;i<=haystack.length()-needle.length();i++){
boolean flag = true;
for(int j=0;j<needle.length();j++){
if(haystack.charAt(i+j)!=needle.charAt(j)){
flag = false;
break;
}
}
if(flag){
return haystack.substring(i);
}
}
return null;
}
Below two solutions is overkill for interview.
third solution: rolling hash
http://blog.csdn/yanghua_kobe/article/details/8914970
fourth solution: KMP
http://www.ruanyifeng/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
strightforward use point scan from begin to end, but this complexity is O(M*N)
char *strStr(char *haystack, char *needle) {
if(!haystack || !needle) return NULL;
int hlength = strlen(haystack);
int nlength = strlen(needle);
if(hlength<nlength) return NULL;
for(int i=0; i<hlength-nlength+1;i++){
char *p = &haystack[i];
int j=0;
for(;j<nlength;j++){
if(*p == needle[j])
p++;
else
break;
}
if(j == nlength)
return &haystack[i];
}
return NULL;
}
the best solution is KMP, complexity is O(N)
版权声明:本文标题:[LeetCode28] Implement strStr() 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dianzi/1729235666a1191957.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论