Medium

题目描述

给你两个字符串 word1 和 word2。

如果你最多可以更改字符串 x 中的一个字符使其与字符串 y 完全相同，那么字符串 x 被称为几乎相等于字符串 y。

如果一个索引序列 seq 满足以下条件，则称其为有效的：

  • 索引按升序排列
  • 将 word1 中这些索引处的字符按相同顺序连接起来，得到一个与 word2 几乎相等的字符串

返回一个大小为 word2.length 的数组，表示字典序最小的有效索引序列。如果不存在这样的索引序列，则返回一个空数组。

注意，答案必须表示字典序最小的数组，而不是由这些索引形成的对应字符串。

示例 1：

输入：word1 = "vbcca", word2 = "abc"
输出：[0,1,2]
解释：字典序最小的有效索引序列是 [0, 1, 2]：
- 将 word1[0] 更改为 'a'
- word1[1] 已经是 'b'
- word1[2] 已经是 'c'

示例 2：

输入：word1 = "bacdc", word2 = "abc"
输出：[1,2,4]
解释：字典序最小的有效索引序列是 [1, 2, 4]：
- word1[1] 已经是 'a'
- 将 word1[2] 更改为 'b'
- word1[4] 已经是 'c'

示例 3：

输入：word1 = "aaaaaa", word2 = "aaabc"
输出：[]
解释：不存在有效的索引序列。

示例 4：

输入：word1 = "abc", word2 = "ab"
输出：[0,1]

约束条件：

  • 1 <= word2.length < word1.length <= 3 * 10^5
  • word1 和 word2 只由小写英文字母组成

解题思路

这道题要求找到字典序最小的有效索引序列，使得按这些索引提取的字符可以通过最多修改一个字符得到 word2。

核心思路是使用动态规划 + 贪心算法：

  1. 预处理阶段：计算 dp 数组，其中 dp[i] 表示从位置 i 开始的 word1 后缀中，能够作为 word2 后缀子序列的最长长度。这样我们就知道在任意位置还能匹配多少个字符。

  2. 贪心选择：从左到右遍历 word1，对于每个位置，贪心地选择能形成字典序最小序列的字符。关键在于判断当前位置是否可以选择：

    • 如果当前字符与目标字符相同，可以直接选择
    • 如果不同，需要检查是否可以用这次修改机会，即后续位置是否还能完成剩余匹配

  3. 修改策略：维护一个 used 变量记录是否已使用修改机会。当遇到不匹配字符时，如果还未使用修改机会且后续能完成匹配，则使用修改机会。

  4. 可行性检查：通过 dp 数组快速判断从当前位置开始是否还能完成剩余的匹配需求。

时间复杂度为 O(n+m)，其中 n 和 m 分别是两个字符串的长度。算法既保证了字典序最小，又确保了解的有效性。

代码实现

class Solution {
public:
    vector<int> validSequence(string word1, string word2) {
        int n = word1.length(), m = word2.length();
        
        // dp[i] = 从位置i开始，word1后缀能匹配word2后缀的最长长度
        vector<int> dp(n + 1, 0);
        int j = m - 1;
        for (int i = n - 1; i >= 0; i--) {
            dp[i] = dp[i + 1];
            if (j >= 0 && word1[i] == word2[j]) {
                dp[i] = dp[i + 1] + 1;
                j--;
            }
        }
        
        // 如果完全无法匹配，返回空数组
        if (dp[0] < m - 1) return {};
        
        vector<int> result;
        bool used = false;
        j = 0;
        
        for (int i = 0; i < n && j < m; i++) {
            if (word1[i] == word2[j]) {
                result.push_back(i);
                j++;
            } else if (!used && dp[i + 1] >= m - j - 1) {
                // 可以使用修改机会
                result.push_back(i);
                used = true;
                j++;
            }
        }
        
        return j == m ? result : vector<int>();
    }
};

class Solution:
    def validSequence(self, word1: str, word2: str) -> List[int]:
        n, m = len(word1), len(word2)
        
        # dp[i] = 从位置i开始，word1后缀能匹配word2后缀的最长长度
        dp = [0] * (n + 1)
        j = m - 1
        for i in range(n - 1, -1, -1):
            dp[i] = dp[i + 1]
            if j >= 0 and word1[i] == word2[j]:
                dp[i] = dp[i + 1] + 1
                j -= 1
        
        # 如果完全无法匹配，返回空数组
        if dp[0] < m - 1:
            return []
        
        result = []
        used = False
        j = 0
        
        for i in range(n):
            if j >= m:
                break
            if word1[i] == word2[j]:
                result.append(i)
                j += 1
            elif not used and dp[i + 1] >= m - j - 1:
                # 可以使用修改机会
                result.append(i)
                used = True
                j += 1
        
        return result if j == m else []

public class Solution {
    public int[] ValidSequence(string word1, string word2) {
        int n = word1.Length, m = word2.Length;
        
        // dp[i] = 从位置i开始，word1后缀能匹配word2后缀的最长长度
        int[] dp = new int[n + 1];
        int j = m - 1;
        for (int i = n - 1; i >= 0; i--) {
            dp[i] = dp[i + 1];
            if (j >= 0 && word1[i] == word2[j]) {
                dp[i] = dp[i + 1] + 1;
                j--;
            }
        }
        
        // 如果完全无法匹配，返回空数组
        if (dp[0] < m - 1) return new int[0];
        
        List<int> result = new List<int>();
        bool used = false;
        j = 0;
        
        for (int i = 0; i < n && j < m; i++) {
            if (word1[i] == word2[j]) {
                result.Add(i);
                j++;
            } else if (!used && dp[i + 1] >= m - j - 1) {
                // 可以使用修改机会
                result.Add(i);
                used = true;
                j++;
            }
        }
        
        return j == m ? result.ToArray() : new int[0];
    }
}

var validSequence = function(word1, word2) {
    const n = word1.length, m = word2.length;
    
    // dp[i] = 从位置i开始，word1后缀能匹配word2后缀的最长长度
    const dp = new Array(n + 1).fill(0);
    let j = m - 1;
    for (let i = n - 1; i >= 0; i--) {
        dp[i] = dp[i + 1];
        if (j >= 0 && word1[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n + m)
空间复杂度O(n)

其中 n 是 word1 的长度，m 是 word2 的长度。预处理 dp 数组需要 O(n) 时间，贪心选择过程需要 O(n) 时间，总体时间复杂度为 O(n + m)。空间复杂度主要来自 dp 数组的存储。

相关题目