28.-shi-xian-strstr.md

28. 实现strStr()

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

解法一：暴力

用两重循环，外层i循环遍历haystack，表示寻找模式串的起点。内层j循环遍历模式串，看haystack[i:j]是否全部符合模式串needle。只要有一个不符合（即haystack[i+j] != needle[j]）全部推倒重来（break）。

此外还要考虑防止数组越界，即当j等于模式串长度的时候，说明匹配成功，返回i。当i+j等于haystack串长度的时候，说明没找到，返回-1。

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        for i in range(len(haystack)+1):
            for j in range(len(needle)+1):
                if j == len(needle):
                    return i
                if i+j == len(haystack):    #防止越界
                    return -1
                if haystack[i+j] != needle[j]:    #有一位不符合
                    break

解法二：对解法一改进

一次循环即可，每次检测len(needle)长度的串

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        for i in range(len(haystack)-len(needle)+1):
            if haystack[i:i+len(needle)] == needle:
                return i
        return -1

此外其实可以偷懒用find函数，一行搞定