leetcode 28 c++ 实现strstr

暴力破解

从前往后找，结果超时了。。。。。。。。。。。。

int strStr(string haystack, string needle) { if (needle.length() == 0) return 0; if (needle.length() > haystack.length()) return -1; int n_index = 0; for (int i = 0; i < haystack.length(); i++) { if (n_index == needle.length()) { return i - needle.length(); } if (haystack[i] == needle[n_index]) { n_index++; } else { if (n_index > 0) { n_index = 0; n_index = 0; //从上一段重合的第二个字符开始找，不然第一段和第二段重合的会让你丢失第一段中后面的元素 i = i - needle.length() + 1; } } } if (n_index < needle.length()) return -1; else if (n_index == needle.length()) return haystack.length() - needle.length(); }

目测输在了每次我比较失败之后都会让 i 回到开始相同的点的后一个位置。来一个复杂度为O(n)的解法。

1、每次比较之前，判断余下的串的长度是否超过子串余下的串的长度

2、两个同步比较，使用continue跳出循环，降低时间复杂度

class Solution { public: int strStr(string haystack, string needle) { if(needle.size()==0) return 0; for(int i=0;i<haystack.size();i++){ if(i+needle.size()-1>=haystack.size()) return -1; int flag=1; for(int j=0;j<needle.size();j++){ if (haystack[i+j]==needle[j]) continue; flag=0; } if (flag==1) return i; } return -1; } };