28. 实现 strStr()
题目
实现strStr()函数。
给定一个haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回-1。
示例 1:
输入: haystack = "hello", needle = "ll"
输出: 2
示例2：
输入: haystack = "aaaaa", needle = "bba"
输出: -1
思路
- 移动 pn 指针，直到 pn 所指向位置的字符与 needle 字符串第一个字符相等。
- 通过 pn，pL，curr_len 计算匹配长度。
- 如果完全匹配（即 curr_len == L），返回匹配子串的起始坐标（即 pn - L）。
- 如果不完全匹配，回溯。使 pn = pn - curr_len + 1， pL = 0， curr_len = 0。
代码
class Solution {
public int strStr(String haystack, String needle) {
int n = haystack.length();
int L = needle.length();
if (L == 0) return 0;
int pn = 0;
while( pn < n-L + 1 ){
//找到第一个一样的元素
while( pn < n-L + 1 && haystack.charAt(pn) != needle.charAt(0) ) ++pn;
//确定一样的元素长度
int currLen = 0, pL = 0;
while( pn < n && pL < L && haystack.charAt(pn) == needle.charAt(pL)){
++pn;
++pL;
++currLen;
}
if(currLen == L) return pn - L;
//回溯
pn = pn - currLen + 1;
}
return -1;
}
}
