Lever's Castle

28. 实现 strStr()

March 27, 2020

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。


Lever

痕迹
没有过去,就没法认定现在的自己