LeetCode 28. 实现 strStr()（易）

字符串匹配的优化问题十分重要，必须知道Sunday、KMP（nuth–Morris–Pratt algorithm）算法。

题目

实现 strStr() 函数 / 字符串匹配问题。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

示例

示例 1: 

1
2
输入: haystack = "hello", needle = "ll"
输出: 2
示例 2: 
1
2
输入: haystack = "aaaaa", needle = "bba"
输出: -1

考察知识点

双指针、字符串

核心思想

这道题虽然简单，但是，字符串匹配是十分基础的问题，相似的字符串匹配算法有 Sunday，KMP，BM，Horspool。

方法一、暴力遍历循环匹配

直接进行暴力循环

方法二、Sunday

匹配机制非常容易理解：

目标字符串String

模式串 Pattern

当前查询索引 idx （初始为 0）

待匹配字符串 str_cut : String [ idx : idx + len(Pattern) ]

每次匹配都会从 目标字符串中 提取 待匹配字符串与 模式串 进行匹配：

若匹配，则返回当前 idx

不匹配，则查看 待匹配字符串紧接着之后的一位字符 c：

1、若c存在于Pattern中，则 idx = idx + 偏移表[c]

2、否则，idx = idx + len(pattern)

Repeat Loop 直到 idx + len(pattern) > len(String)

偏移表的作用是存储每一个在 模式串 中出现的字符，在 模式串 中出现的最右位置到尾部的距离 +1。这个值有什么意义呢？ 举个例子

1
2
3
4
5
6
7
String = "adfaesdsaf"
String_length = 9

Pattern = "faesd"
Pattern_length = 5

pattern偏移表 = {'a': 4, 'd': 1, 'e': 3, 'f': 5, 'ot': 6, 's': 2}

第一次匹配

idx = 0

str_cut = "adfae" = String[idx, idx+Pattern_length] = String[0: 5]

adfae!= faesd

不匹配，则查看 待匹配字符串 的后一位字符 c='s'：

1、若c存在于Pattern中，则 idx = idx + 偏移表[c] 即 idx = 0 + 2 = 2

2、否则，idx = idx + len(pattern)

解释：虽然'adfa''不匹配'fasf'，但是adfae之后的's'就在'faesd'中，偏移量为2，这意味着Pattern中，包含s在内，到结尾处，还有'sd'，两个字符。所以，下一个截取起点，从当前位置开始，往后2个位置，截取的一个长度为5的子串，就刚好能涵盖's'，且让's'在新子串中的位置和's'在Pattern中的位置一样，都在倒数第二个。

第二次匹配

idx = 2

str_cut = "faesd" = String[idx, idx+Pattern_length] = String[2: 7]

faesd == faesd

匹配成功

大佬题解

方法三、KMP

KMP算法和Sunday类似，也是构造了辅助变量，保存Pattern的相对位移关系来解决字符串匹配问题。

具体过程可以参考 动画：七分钟理解什么是KMP算法

Python版本

基于遍历循环的一个版本

自己完成的版本，直接遍历循环，直接做匹配即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        index = -1
        if needle == "":  # 输入的是needle是空串的，直接返回0
            return 0
        if haystack == "":
            return index
        first_char = needle[0]
        needle_len = len(needle)
        haystack_len = len(haystack)
        for i,v in enumerate(haystack):
            if first_char == v and (i + needle_len) <= haystack_len and needle == haystack[i: i+needle_len]:
                index = i
                break
        return index


print("leet code accept!!!")
Input = ["a", "a", "", "hello", "aaaaa"]
Input1 = ["a", "", "", "ll", "bba"]
Answer = [0, 0, 0, 2, -1]

if __name__ == "__main__":
    solution = Solution()
    for i in range(len(Input)):
        print("-"*50)
        result = solution.strStr(Input[i], Input1[i])
        print(result==Answer[i])

时间复杂度 O(n)
空间复杂度 O(1)
执行用时 :32 ms, 在所有 Python3 提交中击败了82.59%的用户
内存消耗 :13.4 MB, 在所有 Python3 提交中击败了40.08%的用户

Sunday

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:

        # Func: 计算偏移表
        def calShiftMat(st):
            dic = {}
            for i in range(len(st)-1,-1,-1):  # 从后往前计算
                if not dic.get(st[i]):
                    dic[st[i]] = len(st)-i
            dic["ot"] = len(st)+1
            return dic
        
        needle_len = len(needle)
        haystack_len = len(haystack)

        # 其他情况判断
        if needle_len > haystack_len:return -1
        if needle=="": return 0
       
        # 偏移表预处理
        dic = calShiftMat(needle)
        idx = 0
         
    
        while idx+needle_len <= haystack_len:
            
            # 待匹配字符串
            str_cut = haystack[idx:idx+needle_len]
            
            # 判断是否匹配
            if str_cut==needle:
                return idx
            else:
                # 边界处理
                if idx+needle_len >= haystack_len:
                    return -1
                # 不匹配情况下，根据下一个字符的偏移，移动idx
                cur_c = haystack[idx+needle_len]
                if dic.get(cur_c):
                    idx += dic[cur_c]
                else:
                    idx += dic["ot"]
            
        
        return -1 if idx+needle_len >= haystack_len else idx

时间复杂度：O(nm)或O(n)
执行用时 :32 ms, 在所有 Python3 提交中击败了82.59%的用户
内存消耗 :13.5 MB, 在所有 Python3 提交中击败了40.03%的用户

KMP算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution:
    def strStr(self, haystack: str, needle: str) -> int: 
        def get_next(p): 
            """ 构造子串needle的匹配表, 以 "ABCDABD" 为例
            i         i          i           i            i             i             i
            ABCDABD  ABCDABD   ABCDABD    ABCDABD     ABCDABD      ABCDABD      ABCDABD
            ABCDABD   ABCDABD    ABCDABD     ABCDABD      ABCDABD      ABCDABD        ABCDABD
            j         j          j           j            j             j             j
            """
            _next = [0] * (len(p)+1) #      A  B  C  D  A  B  D
            _next[0] = -1            # [-1, 0, 0, 0, 0, 1, 2, 0]
            i, j = 0, -1
            while (i < len(p)):
                if (j == -1 or p[i] == p[j]):
                    i += 1
                    j += 1 
                    _next[i] = j
                else:
                    j = _next[j]
            return _next
        
        def kmp(s, p, _next):
            """kmp O(m+n). s以 "BBC ABCDAB ABCDABCDABDE" 为例"""
            i, j = 0, 0
            while (i < len(s) and j < len(p)):
                if (j == -1 or s[i] == p[j]):
                    i += 1
                    j += 1
                else:
                    j = _next[j]
            if j == len(p):
                return i - j
            else:
                return -1
            
        return kmp(haystack, needle, get_next(needle))

返回一个字符串中所有结果的方法 strStrs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Solution:
    def strStrs(self, haystack: str, needle: str) -> list:
        res = []
        # count = 0
        if len(haystack) == 0:
            return res
        last_index = 0
        is_first = True
        while haystack:
            tmp_index = self.strStr(haystack, needle)
            if tmp_index != -1:  # 如果找到了就保存到res里面
                if is_first:  # 第一次
                    res.append(tmp_index)
                    last_index = tmp_index
                    is_first = False
                else:
                    res.append(tmp_index + last_index + 1)
                    last_index = tmp_index + last_index + 1
                haystack = haystack[tmp_index+1: ]
                # count += 1
            else:  # 如果一次都找不到，就直接返回[]
                return res
        return res

    def strStr(self, haystack: str, needle: str) -> int:
        # Func: 计算偏移表
        def calShiftMat(st):
            dic = {}
            for i in range(len(st)-1,-1,-1):  # 从后往前计算
                if not dic.get(st[i]):
                    dic[st[i]] = len(st)-i
            dic["ot"] = len(st)+1
            return dic

        needle_len = len(needle)
        haystack_len = len(haystack)

        # 其他情况判断
        if needle_len > haystack_len:return -1
        if needle=="": return 0
       
        # 偏移表预处理
        dic = calShiftMat(needle)
        idx = 0

        while idx+needle_len <= haystack_len:
            # 待匹配字符串
            str_cut = haystack[idx:idx+needle_len]
            # 判断是否匹配，如果匹配了就把答案填在res里面，并递归调用，直到再也找不到为止。
            if str_cut==needle:
                return idx
            else:
                # 边界处理
                if idx+needle_len >= haystack_len:
                    return -1
                # 不匹配情况下，根据下一个字符的偏移，移动idx
                cur_c = haystack[idx+needle_len]
                if dic.get(cur_c):
                    idx += dic[cur_c]
                else:
                    idx += dic["ot"]

        return -1 if idx+needle_len >= haystack_len else idx