admin管理员组文章数量:1636904
Implement strStr().
Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack。
leetcode上面的一道题。就是一个字符串中是否存在子串和给定的另外一个字符串相等。如果相等,返回该子串首字母的索引。不存在就返回-1。
这道题最容易想到的就是暴力求解。即遍历haystack中的元素。如果某个元素和needle的首元素相等,那么接着比较needle的下一个元素。如果needle中的元素完全匹配,则返回。否则继续遍历haystack中的元素和needle首元素比较。相等,则重复上述过程,不等,继续往下走。代码如下:
int strStr(string haystack, string needle) {
int length_h=haystack.size();
int length_n=needle.size();
if(length_n==0)
{
return 0;
}
if(length_h<length_n)
{
return -1;
}
int n=0;
for(int i=0;i<length_h-length_n+1;i++)
{
if(haystack[i]==needle[n])
{
int j=1;
for(;j<length_n;j++)
{
if(haystack[i+j]!=needle[j])
{
break;
}
}
if(j==length_n)
return i;
}
}
return -1;
}
这道题最经典的解法应该是KMP算法。
这里有一个关于KMP算法的比较通俗易懂的解释。链接如下:
http://wwwblogs/c-cloud/p/3224788.html。
版权声明:本文标题:Implement strStr()--leetcode 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dianzi/1729235295a1191922.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论