28. 實現(xiàn) strStr()
題目
實現(xiàn)strStr()函數(shù)嫁乘。
給定一個haystack 字符串和一個 needle 字符串你雌，在 haystack 字符串中找出 needle 字符串出現(xiàn)的第一個位置 (從0開始)。如果不存在玻粪，則返回-1周叮。
示例 1:
輸入: haystack = "hello", needle = "ll"
輸出: 2
示例2：
輸入: haystack = "aaaaa", needle = "bba"
輸出: -1
思路
- 移動 pn 指針揩尸，直到 pn 所指向位置的字符與 needle 字符串第一個字符相等所禀。
- 通過 pn方面，pL申钩，curr_len 計算匹配長度虑粥。
- 如果完全匹配（即 curr_len == L），返回匹配子串的起始坐標(biāo)（即 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;
}
}
