找出字符串中第一个匹配项的下标-LeetCode

找出字符串中第一个匹配项的下标

🎯 问题描述（来源于LeetCode）

描述：
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回  -1 。
说明：

• 1 <= haystack.length, needle.length <= 104
• haystack 和 needle 仅由小写英文字符组成

示例：

• 示例 1：

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

• 示例 2：

输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

💻 解题思路

思路1：BF算法

思路1：代码实现

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        n,m=len(haystack),len(needle)
        i,j=0,0
        while i < n and j < m:
            if haystack[i]==needle[j]:
                i+=1
                j+=1
            else:
                i=i-j+1
                j=0
        if j==m:
            return i-j
        else:
            return -1

思路1：📊 性能分析

提交结果

• 运行时间：0ms击败100.00%
• 内存消耗：19.01MB击败65.73%

复杂度验证

• 时间复杂度：$O(n*m)$
• 空间复杂度：$O(1)$

思路2：RK算法

思路2：代码实现

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        n,m=len(haystack),len(needle)
        hash_p=hash(needle)
        for i in range(n-m+1):
            hash_t=hash(haystack[i:i+m])
            if hash_t!=hash_p:
                continue
            len_str=0
            for j in range(m):
                if haystack[i+j]!=needle[j]:
                    break
                len_str+=1
                if len_str==m:
                    return i
        return -1

思路2：📊 性能分析

提交结果

• 运行时间：4ms击败12.95%
• 内存消耗：19.13MB击败44.96%

复杂度验证

• 时间复杂度：$O(N∗M)$
• 空间复杂度：$O(M)$

思路3：KMP算法

思路3：代码实现

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        def generateNext(p:str):
            m = len(p)
            next = [0 for _ in range(m)]
            left = 0
            for right in range(1,m):
                while left > 0 and p[left]!=p[right]:
                    left=next[left-1]
                if p[left]==p[right]:
                    left+=1
                next[right]=left
            return next
        n,m=len(haystack),len(needle)
        if m == 0:
            return 0
        next=generateNext(needle)
        j =0
        for i in range(n):
            while j >0 and haystack[i]!=needle[j]:
                j=next[j-1]
            if haystack[i]==needle[j]:
                j+=1
            if j == m:
                return i-m+1
        return -1

思路3：📊 性能分析

提交结果

• 运行时间：3ms击败31.69%
• 内存消耗：19.40MB击败10.48%

复杂度验证

• 时间复杂度：$O(N+M)$
• 空间复杂度：$O(1)$

思路4：BM算法

思路4：代码实现

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        def boyerMoore(T: str, p: str) -> int:
            n, m = len(T), len(p)
            if m == 0:
                return 0
            btable = generate_btable(p)
            gtable = generate_gtable(p)
            i = 0
            while i <= n - m:
                j = m - 1
                while j >= 0 and T[i + j] == p[j]:
                    j -= 1
                if j < 0:
                    return i
                b_move = j - btable.get(T[i + j], -1)
                g_move = gtable[j]  
                i += max(b_move, g_move)
            return -1
        def generate_btable(p: str):
            b_table = {}
            for i, ch in enumerate(p):
                b_table[ch] = i
            return b_table
        def generate_gtable(p: str):
            m = len(p)
            gtable = [m for _ in range(m)]
            suffix = generatesuffix(p)
            j = 0
            for i in range(m - 1, -1, -1):
                if suffix[i] == i + 1:
                    while j < m - 1 - i:
                        if gtable[j] == m:
                            gtable[j] = m - 1 - i
                        j += 1
            for i in range(m - 1):
                gtable[m - 1 - suffix[i]] = m - 1 - i
            return gtable
        def generatesuffix(p: str):
            m = len(p)
            suffix = [m for _ in range(m)]
            suffix[m - 1] = m
            for i in range(m - 2, -1, -1):
                j = i
                while j >= 0 and p[j] == p[m - 1 - i + j]:
                    j -= 1
                suffix[i] = i - j
            return suffix
        return boyerMoore(haystack, needle)

思路4：📊 性能分析

提交结果

• 运行时间：3ms击败31.67%
• 内存消耗：19.36MB击败13.33%

复杂度验证

• 时间复杂度：$O(N*M)$
• 空间复杂度：$O(M)$

思路5：Horspool 算法

思路5：代码实现

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        def Horspool(T:str,p:str)->int:
        	n,m=len(T),len(p)
        	if m == 0:
        		return 0
        	move={}
        	for i in range(m-1):
        		move[p[i]]=m-1-i
        	i = m-1
        	while i < n:
        		k= m-1
        		while k >= 0 and T[i-(m - 1 - k)]==p[k] :
        			k-=1
        		if k < 0:
        			return i - m + 1
        		else :
        			i += move.get(T[i],m)
        	return -1	
        return Horspool(haystack, needle)

思路5：📊 性能分析

提交结果

• 运行时间：3ms击败31.61%
• 内存消耗：19.03MB击败65.97%

复杂度验证

• 时间复杂度：$O(N*M)$
• 空间复杂度：$O(1)$

思路6：Sunday 算法

思路6：代码实现

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        def Sunday(T: str, p: str) -> int:
            n, m = len(T), len(p)
            if m == 0:
                return 0
            # 构建位移表（记录每个字符在模式串中最右出现的位置）
            lastPos = {}
            for i in range(m):
                lastPos[p[i]] = i
            i = 0
            while i <= n - m:
                j = 0
                # 从左到右比较
                while j < m and T[i + j] == p[j]:
                    j += 1
                if j == m:
                    return i
                # 失配，查看窗口后的下一个字符
                if i + m < n:
                    next_char = T[i + m]
                    # 移动步数 = m - 该字符在模式串中最右位置（若不存在则为 -1）
                    step = m - lastPos.get(next_char, -1)
                else:
                    break
                i += step
            return -1
        return Sunday(haystack, needle)

思路6：📊 性能分析

提交结果

• 运行时间：0ms击败100.00%
• 内存消耗：19.15MB击败44.91%

复杂度验证

• 时间复杂度：$O(N*M)$
• 空间复杂度：$O(M)$