admin管理员组文章数量:1637068
Title:
Implement strStr().
Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
这道题是实现c的库函数,strstr(str1,str2),也就是返回子字符串str2在str1中第一次出现的位置,如果没有,则返回-1。思路如下:首先在字符串str1中找str2的第一个字符,如果存在,再进一步比较str2后面的字符与str1后面的字符是否相等。很容易的一道题。
solution:
int strStr(char* haystack, char* needle) {
int i=0;
int j=1;
int res,tmp;
int flag=0;
if (!needle[0])
return 0;
while (haystack[i]) {
flag=0;
j=1;
if (needle[0]==haystack[i]) {
res=i;
tmp=i+1;
while (needle[j]) {
if (needle[j] && !haystack[tmp])
return -1;
if (needle[j]==haystack[tmp]) {
tmp++;
j++;
}
else {
flag=1;
break;
}
}
if (flag==0)
return res;
}
i++;
}
return -1;
}
要注意到一些细节。
1.如果子字符串为空,那么返回0。
2.如果子字符串的长度大于母字符串,那么不用比对,直接输出-1,这样能够大大降低时间开销。那么如何知道他们的长度,如果用while循环,分别得出它们的长度,固然可取,但由于两个while遍历字符串,时间开销会大大增加,得不偿失。
因此本人采用的办法如下:
if (needle[j] && !haystack[tmp])
return -1;
在比对过程中,如果needle的某个字符不为0,也就是没有到最后,而母字符串haystack的字符为0,也就是此时haystack已经到了最后,此时,needle一定不存在于haystack中,返回0。
下图是采用了长度判断和没有采用的运行时间对比:
可以看出采用了长度判断,时间开销大大减少。
本文标签: 语言LeetCodestrStrimplement
版权声明:本文标题:Leetcode c语言-Implement strStr() 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/xitong/1729233876a1191767.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论