admin管理员组文章数量:1636902
题目如下
Implement strStr()
Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.
题目分析
就是实现strstr()一遍,如果不使用KMP,那么就老老实实地逐个比较。
//12ms
class Solution {
public:
char *strStr(char *haystack, char *needle) {
if(needle==NULL||*needle=='\0')
return haystack;
int length=(int)strlen(needle);//如果要获得长度,用strlen,否则sizeof(*needle)/sizeof(char),结果永远为固定值,因为needle参数表示的是一个指针变量,
char* p_res=NULL;
char* needle_start=needle;
for(;*haystack!='\0';haystack++){
if(*haystack==*needle){
needle++;
if(*needle=='\0')
break;
}else{
int already_len=(int)(needle-needle_start);
if(already_len==0) {
continue;
} else {
haystack=haystack-already_len; //回溯
needle=needle_start;//回溯
}
}
}
p_res=haystack-length+1;
if(*needle=='\0')
return p_res;
else
return NULL;
}
};
上面的代码居然12ms过了大集合。按说这个算法的时间复杂度是很高的。
如果不使用KMP,如果使用上面的逐渐比较每个字符的方法,那么时间复杂度最坏情况下位O(M*N),其中M和N分别为haystack和needle的长度。如果使用KMP,时间复杂度降为O(M+N).
KMP算法的实现稍后写出。
update: 2015-01-06
OJ 把函数的返回值由char* 改为了int,
//8ms
class Solution {
public:
int strStr(char *haystack, char *needle) {
if (*haystack == '\0' && *needle == '\0') return 0;
if (*haystack == '\0' && *needle != '\0') return -1;
int index = 0;
int result = 0;
char* needle_pointer = needle;
char* haystack_pointer = haystack;
while (*haystack_pointer != '\0') {
//std::cout<<"hay:"<<haystack_pointer<<", needle:"<<needle_pointer<<", index:"<<index<<std::endl;
while (*haystack_pointer != '\0' &&
*needle_pointer!= '\0' &&
*haystack_pointer == *needle_pointer ) {
++haystack_pointer;
++needle_pointer;
}
if (*needle_pointer == '\0') return index;
else if (*haystack_pointer == '\0') return -1;
else {
index = index + 1;
haystack_pointer = haystack + index;
needle_pointer = needle;
}
}
return -1;
}
};
版权声明:本文标题:LeetCode(28)Implement Strstr() 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dongtai/1729235017a1191891.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论