Leetcode 3303. Find the Occurrence of First Almost Equal Substring

• Leetcode 3303. Find the Occurrence of First Almost Equal Substring
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3303. Find the Occurrence of First Almost Equal Substring

1. 解题思路

这道题的话思路上和上一题相仿，由于都是只能调整至多一个位置，因此，我们就是考察每一个位置前后最大的前序公共子序列以及后续的最大公共子序列的长度。

假设目标字符串word2的长度为$m$，若某个位置与word2的最长公共前序数组的长度为$k$。

• 若$k\ge m$，那么该位置直接就是我们的一个答案
• 若$k<m$，且从该位置开始的第$k+2$到第$m$的恰好与word2的后$m-k-1$个字符相一致，那么通过调整第$k$个字符，同样可以得到word2

由此，我们通过构造正向和负向的最大公共子串长度即可快速地求得任意一个位置是否满足条件，然后我们从中找到第一个符合题意的位置即可。

而对于任意方向的最大公共子串长度的计算方法，我们可以通过z算法进行实现，对应的内容网上有不少，我也写过一篇博客（经典算法：Z算法（z algorithm））对其进行简单介绍，这里就不过多展开了。

2. 代码实现

给出python代码实现如下：

def z_algorithm(s):
    n = len(s)
    z = [0 for _ in range(n)]
    l, r = -1, -1
    for i in range(1, n):
        if i > r:
            l, r = i, i
            while r < n and s[r-l] == s[r]:
                r += 1
            z[i] = r-l
            r -= 1
        else:
            k = i - l
            if z[k] < r - i + 1:
                z[i] = z[k]
            else:
                l = i
                while r < n and s[r-l] == s[r]:
                    r += 1
                z[i] = r-l
                r -= 1
    z[0] = n
    return z

class Solution:
    def minStartingIndex(self, s: str, pattern: str) -> int:
        n, m = len(s), len(pattern)
        z1 = z_algorithm(pattern + s)
        z2 = z_algorithm(pattern[::-1] + s[::-1])
        for i in range(n):
            if i+m > n:
                break
            c1 = z1[i+m]
            if c1 >= m:
                return i
            j = i+m-1
            c2 = z2[n-j-1+m]
            if c1 + c2 == m-1:
                return i
        return -1

提交代码评测得到：耗时2756ms，占用内存50.4MB。