学习
实践
活动
工具
TVP
写文章

10.实现strStr

题号28:

实现strStr()。

返回蕴含在 haystack 中的 needle 的第一个字符的索引,如果 needle 不是 haystack 的一部分则返回-1 。

例 1:

输入:haystack = "hello", needle = "ll"

输出:2

例 2:

输入:haystack = "aaaaa", needle = "bba"

输出:-1

解题思路:

模式匹配。用了最简单粗暴的办法,之前学过KMP及其改进算法,但暂时写不出对应程序,二刷的时候再贴改进版。

遍历给定字符串haystack,当某个字符haystack[i]与needle[0]相同时,遍历needle,判断needle是否是haystack的一部分;

若needle[j]与haystack[i+j]有一个字符不匹配,则跳出needle的遍历,继续向前遍历haystack;

若needle[j]与haystack[i+j]都匹配(即needle中的字符已全部遍历,此时j==needle的长度),则返回当前的位置i。

代码实现:

class Solution {

public:

int strStr(string haystack, string needle) {

if(needle.length()==0) return 0;

for(int i=0;i

if(haystack[i]==needle[0]){

int j=0;

for(;j

if(haystack[i+j]!=needle[j]){

break;

}

}

if(j==needle.length()){

return i;

}

}

}

return -1;

}

};

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180407G0J4TV00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码关注腾讯云开发者

领取腾讯云代金券