博文中会简要介绍Leetcode P0028题目分析及解题思路。
“Implement strStr()”是一道可复杂可简单的题目，复杂但是高效的解法是使用KMP算法，不过在这篇博文里不展开解释，后续可能会有专门针对KMP算法的博文，详细介绍。
Implement strStr().
Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
这道题的思路比较直接，时间复杂度是O(n^2)。
以下是Java的题解代码实现。
class Solution {
public int strStr(String haystack, String needle) {
if (needle == null || needle.length() == 0)
return 0;
if (haystack.length() < needle.length())
return -1;
char[] haystackChars = haystack.toCharArray();
char[] needleChars = needle.toCharArray();
for (int i1=0; i1<=haystackChars.length-needleChars.length; ++i1) {
int j2 = i1;
for (int k3=0; k3<needleChars.length; ++k3) {
if (j2 >= haystackChars.length || haystackChars[j2] != needleChars[k3])
break;
++j2;
}
if (j2-i1 == needleChars.length)
return i1;
}
return -1;
}
}
以下是C++的题解代码实现。
class Solution {
public:
int strStr(string haystack, string needle) {
if (needle.length() == 0)
return 0;
if (haystack.length() < needle.length())
return -1;
for (int i1=0; i1<=haystack.length()-needle.length(); ++i1) {
int j2 = i1;
for (int k3=0; k3<needle.length(); ++k3) {
if (j2 >= haystack.length() || haystack[j2] != needle[k3])
break;
++j2;
}
if (j2-i1 == needle.length())
return i1;
}
return -1;
}
};