28.md

title	date
28. 实现 strStr()	2020-03-27T22:35:00.000Z

https://leetcode-cn.com/problems/implement-strstr/

解：

func strStr(haystack string, needle string) int {
    if len(haystack) < len(needle) {
        return -1
    }
    var i, j int
    for i < len(haystack) {
        if j >= len(needle) {
            return i - j
        }
        if haystack[i] == needle[j] {
            j++
            i++
        } else {
            i = i - j + 1
            j = 0
        }
    }

    if j == len(needle) {
        return i - j
    }
    return -1
}

题目比较简单，就是边界条件不好处理。用 i 和 j 分别控制 haystack 和 needle 的遍历进度，并挨个比较。相等的话两者继续向后比较，不相等，就重置 j，并将 i 移动到本轮的开始位置的下一元素，重新与 needle 进行比较。

匹配成功的条件有两种，一种是 needle 已经遍历完成，haystack 还没遍历完成，此时直接返回 i - j 即为开始位置的索引。一种是 needle 和 haystack 同时遍历完成，同样也返回 i - j 即可。只要遍历完成并且 j 的大小与 needle 长度不同，就可以认为没有匹配成功，返回 -1。