admin管理员组文章数量:1636897
题目链接:https://leetcode/problems/implement-strstr/
Implement strStr().
Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
思路:按照简单的做可以很简单,就是找一个字符串中是否包含另一个字符串,并返回其位置。按照复杂的做那么就是KMP了, 所以 看出题人的意思了.
代码如下:
class Solution {
public:
int strStr(string haystack, string needle) {
int i = -1, len1 = haystack.size(), len2 = needle.size();
while(++i <= len1-len2)
{
string tem = haystack.substr(i, len2);
if(tem == needle) return i;
}
return -1;
}
};
KMP
class Solution {
public:
int strStr(string haystack, string needle) {
int i, k = 0, len1 = haystack.size(), len2 = needle.size();
if(len2==0 || haystack == needle) return 0;
vector<int> index(len2, 0);
for(i = 1; i < len2; i++)
{
while(k>0 && needle[i]!=needle[k]) k = index[k-1];
index[i] = (k+=needle[i]==needle[k]);
}
for(i = 0, k = 0; i < len1; i++)
{
while(k>0 && haystack[i]!=needle[k]) k = index[k-1];
k += needle[k] == haystack[i];
if(k == len2) return i-len2+1;
}
return -1;
}
};
本文标签: 报告LeetCodestrStrimplement
版权声明:本文标题:[leetcode] 28. Implement strStr() 解题报告 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dongtai/1729233986a1191777.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论