问题
Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Example 1:
Input: haystack = "hello", needle = "ll"
Output: 2
Example 2:
Input: haystack = "aaaaa", needle = "bba"
Output: -1
思路
比较容易想到的思路,假设原串的长度是n,匹配串的长度是m。对原串的每一个长度为m的字串都判断是否跟匹配串一致。总共有n-m+1个子串,算法时间复杂度为O((n-m+1)m)=O(nm)
一开始,两个边界条件没有想清楚。i的范围为n-m+1,因为子串的个数为n-m+1个。
class Solution {
public:
int strStr(string haystack, string needle) {
if(needle.empty())
{
return 0;
}
int m = haystack.size();
int n = needle.size();
if(m < n)
{
return -1;
}
for(int i = 0; i < m - n + 1; ++i)
{
int j = 0; //在for外面定义j,j用于计数,减少一个变量的定义
for(j = 0; j < n; ++j)
{
if(needle[j] != haystack[i + j])
{
break;
}
}
if(j == needle.size())
{
return i;
}
}
return -1;
}
};
有时间的话,使用KMP算法实现一遍。KMP读一遍,过一段时间又忘,简直了。