实现 类似Java中indexOf() 函数。
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
示例 1:
输入: haystack = "hello", needle = "ll"
输出: 2说明:
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。思路一：截串比较，每次从haystack中substring(i,needle.length)和needle比较，知道发现相等，返回下标i
/**
* 子串匹配
* @param haystack
* @param needle
* @return
*/
public static int strStr(String haystack, String needle) {
int L = needle.length(), n = haystack.length();
for (int start = 0; start < n - L + 1; ++start) {
if (haystack.substring(start, start + L).equals(needle)) {
return start;
}
}
return -1;
}上面的代码是非常精简的，如果思路不好理解，可以参考第二个版本
/**
* 子串匹配
* @param haystack
* @param needle
* @return
*/
public static int strStr(String haystack, String needle) {
if (needle == null || "".equals(needle)) {
return 0;
}
//如果haystack长度小于needle,那肯定不匹配
if(needle.length()>haystack.length()) {
return -1;
}
for(int i=0;i<haystack.length();i++) {
//如果截取末位超过字符串长度,说明没有子串
if(i+needle.length()>haystack.length()) {
return -1;
}
//判断子串是否匹配
if(haystack.substring(i,i+needle.length()).equals(needle)) {
return i;
}
}
return -1;
}思路二：用回溯查找，进行子串匹配。上面的子串查找的缺点是每次向后移动一个位置,截取子串开始匹配，这里的思路是将两个字符串拆开,按照字符比较,从开头字符开始比较,不相等则后移,继续比较，这里为什么叫回溯,因为如果比较到两个字符串中间位置,发现不匹配了,则要往回退,退到本次比较的头字符的下一个位置，重新开始逐个字符比较。
/**
* 回溯查找
* 上面的子串查找的缺点是每次向后移动一个位置,截取子串开始匹配
* 这里的思路是将两个字符串拆开,按照字符比较,从开头字符开始比较,不相等则后移,继续比较
* 这里为什么叫回溯,因为如果比较到两个字符串中间位置,发现不匹配了,则要往回退,
* 退到本次比较的头字符的下一个位置，重新开始逐个字符比较
* 例如：haystack="aabsikm",needle="absi"
* a a b s i k m
* | |
* a b s i
* 第一次比较从aabsikm的下标为0的位置开始，检测到第二个字符，发现不匹配，此时aabsikm指针向后移一位
*
* a a b s i k m
* | | | |
* a b s i
*
* @param haystack
* @param needle
* @return
*/
public static int strStr3(String haystack, String needle) {
int L = needle.length(), n = haystack.length();
if(L == 0) {
return 0;
}
int pn = 0;
while(pn < n-L+1) {
//判断起始字符串是否相等,不相等则haystack指针后移一位,继续比较
while(pn < n-L+1 && haystack.charAt(pn) != needle.charAt(0)) pn++;
//有相等的起始字符,则开始比较后续字符是否相等
int curnLen=0, pL=0;
while(pn < n && pL<L && haystack.charAt(pn) == needle.charAt(pL)) {
pn++;
pL++;
//curnLen作用就是用作最后计算字符串是否匹配,
// 如果curnLen长度等于needle的长度,
// 说明匹配到了最后,也就存在子串
curnLen++;
}
if(curnLen == L) {
return pn-L;
}
//如果上面的while循环（while(pn < n-L+1 && haystack.charAt(pn) == needle.charAt(pL))）发现不匹配,
// 这时候就要回退了,继续比较
pn = pn - curnLen + 1;
}
return -1;
}除了上面两种，还有多种方法来处理这个问题，比如KMP算法，只是这种算法不是太好理解，如果要讲解，要用单独的篇幅来讲，在这里暂时先不展开，有兴趣的可以试一试。
还有一种妖娆的写法，时间效率超过了leetcode平台100%的用户
public static int strStr4(String haystack, String needle) {
return haystack.indexOf(needle);
}O(∩_∩)O哈哈~