Hard

题目描述

给你两个字符串 s 和 pattern。

如果你最多只能修改字符串 x 中的一个字符使其与 y 相同，那么我们称字符串 x 几乎等于 y。

返回字符串 s 中几乎等于 pattern 的子串的最小起始索引。如果不存在这样的索引，返回 -1。

子串是字符串中连续的非空字符序列。

示例 1：

输入：s = "abcdefg", pattern = "bcdffg"
输出：1
解释：子串 s[1..6] == "bcdefg" 可以通过将 s[4] 改为 "f" 转换为 "bcdffg"。

示例 2：

输入：s = "ababbababa", pattern = "bacaba"
输出：4
解释：子串 s[4..9] == "bababa" 可以通过将 s[6] 改为 "c" 转换为 "bacaba"。

示例 3：

输入：s = "abcd", pattern = "dba"
输出：-1

示例 4：

输入：s = "dde", pattern = "d"
输出：0

约束条件：

  • 1 <= pattern.length < s.length <= 10^5
  • s 和 pattern 仅由小写英文字母组成

进阶： 如果最多可以修改 k 个连续字符，你能解决这个问题吗？

解题思路

这道题的关键是理解题目提示中的动态规划思想。我们需要预处理两个数组：

  1. dp1[i]：从位置 i 开始的子串与 pattern 前缀匹配的最大长度
  2. dp2[i]：以位置 i 结尾的子串与 pattern 后缀匹配的最大长度

核心思路是：对于长度为 pattern.length 的窗口，如果在某个位置 i，满足 dp1[i] + dp2[i + pattern.length - 1] >= pattern.length - 1，说明这个窗口中最多只有一个位置不匹配，即几乎相等。

算法步骤：

  1. 使用 Z 算法计算 pattern + s 的 Z 数组，得到 dp1
  2. 使用 Z 算法计算 reverse(pattern) + reverse(s) 的 Z 数组，得到 dp2
  3. 遍历所有可能的起始位置，检查是否满足几乎相等条件

Z 算法可以在 O(n) 时间内计算字符串的所有前缀与后缀的最长公共前缀，这里用来高效计算前缀和后缀匹配长度。

时间复杂度 O(n)，空间复杂度 O(n)，其中 n = s.length + pattern.length。

代码实现

class Solution {
public:
    vector<int> computeZ(const string& str) {
        int n = str.length();
        vector<int> z(n);
        int l = 0, r = 0;
        
        for (int i = 1; i < n; i++) {
            if (i <= r) {
                z[i] = min(r - i + 1, z[i - l]);
            }
            while (i + z[i] < n && str[z[i]] == str[i + z[i]]) {
                z[i]++;
            }
            if (i + z[i] - 1 > r) {
                l = i;
                r = i + z[i] - 1;
            }
        }
        
        return z;
    }
    
    int minStartingIndex(string s, string pattern) {
        int n = s.length();
        int m = pattern.length();
        
        // 计算 dp1: 从每个位置开始与 pattern 前缀的匹配长度
        string combined1 = pattern + s;
        vector<int> z1 = computeZ(combined1);
        vector<int> dp1(n);
        for (int i = 0; i < n; i++) {
            dp1[i] = z1[m + i];
        }
        
        // 计算 dp2: 到每个位置结束与 pattern 后缀的匹配长度
        string rev_pattern = pattern;
        reverse(rev_pattern.begin(), rev_pattern.end());
        string rev_s = s;
        reverse(rev_s.begin(), rev_s.end());
        string combined2 = rev_pattern + rev_s;
        vector<int> z2 = computeZ(combined2);
        vector<int> dp2(n);
        for (int i = 0; i < n; i++) {
            dp2[n - 1 - i] = z2[m + i];
        }
        
        // 检查每个可能的起始位置
        for (int i = 0; i <= n - m; i++) {
            if (dp1[i] + dp2[i + m - 1] >= m - 1) {
                return i;
            }
        }
        
        return -1;
    }
};

class Solution:
    def compute_z(self, s):
        n = len(s)
        z = [0] * n
        l = r = 0
        
        for i in range(1, n):
            if i <= r:
                z[i] = min(r - i + 1, z[i - l])
            while i + z[i] < n and s[z[i]] == s[i + z[i]]:
                z[i] += 1
            if i + z[i] - 1 > r:
                l = i
                r = i + z[i] - 1
        
        return z
    
    def minStartingIndex(self, s: str, pattern: str) -> int:
        n = len(s)
        m = len(pattern)
        
        # 计算 dp1: 从每个位置开始与 pattern 前缀的匹配长度
        combined1 = pattern + s
        z1 = self.compute_z(combined1)
        dp1 = [z1[m + i] for i in range(n)]
        
        # 计算 dp2: 到每个位置结束与 pattern 后缀的匹配长度
        rev_pattern = pattern[::-1]
        rev_s = s[::-1]
        combined2 = rev_pattern + rev_s
        z2 = self.compute_z(combined2)
        dp2 = [0] * n
        for i in range(n):
            dp2[n - 1 - i] = z2[m + i]
        
        # 检查每个可能的起始位置
        for i in range(n - m + 1):
            if dp1[i] + dp2[i + m - 1] >= m - 1:
                return i
        
        return -1

public class Solution {
    private int[] ComputeZ(string str) {
        int n = str.Length;
        int[] z = new int[n];
        int l = 0, r = 0;
        
        for (int i = 1; i < n; i++) {
            if (i <= r) {
                z[i] = Math.Min(r - i + 1, z[i - l]);
            }
            while (i + z[i] < n && str[z[i]] == str[i + z[i]]) {
                z[i]++;
            }
            if (i + z[i] - 1 > r) {
                l = i;
                r = i + z[i] - 1;
            }
        }
        
        return z;
    }
    
    public int MinStartingIndex(string s, string pattern) {
        int n = s.Length;
        int m = pattern.Length;
        
        // 计算 dp1: 从每个位置开始与 pattern 前缀的匹配长度
        string combined1 = pattern + s;
        int[] z1 = ComputeZ(combined1);
        int[] dp1 = new int[n];
        for (int i = 0; i < n; i++) {
            dp1[i] = z1[m + i];
        }
        
        // 计算 dp2: 到每个位置结束与 pattern 后缀的匹配长度
        char[] revPattern = pattern.ToCharArray();
        Array.Reverse(revPattern);
        char[] revS = s.ToCharArray();
        Array.Reverse(revS);
        string combined2 = new string(revPattern) + new string(revS);
        int[] z2 = ComputeZ(combined2);
        int[] dp2 = new int[n];
        for (int i = 0; i < n; i++) {
            dp2[n - 1 - i] = z2[m + i];
        }
        
        // 检查每个可能的起始位置
        for (int i = 0; i <= n - m; i++) {
            if (dp1[i] + dp2[i + m - 1] >= m - 1) {
                return i;
            }
        }
        
        return -1;
    }
}

var minStartingIndex = function(s, pattern) {
    const n = s.length;
    const m = pattern.length;
    
    for (let i = 0; i <= n - m; i++) {
        let diff = 0;
        for (let j = 0; j < m; j++) {
            if (s[i + j] !== pattern[j]) {
                diff++;
                if (diff > 1) break;
            }
        }
        if (diff <= 1) {
            return i;
        }
    }
    
    return -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

项目复杂度
时间复杂度O(n + m)
空间复杂度O(n + m)

其中 n 为字符串 s 的长度，m 为 pattern 的长度。Z 算法的时间复杂度是线性的，整个算法需要计算两次 Z 数组并遍历一次结果。

相关题目