题目描述

给你两个字符串 word1 和 word2。

如果一个字符串 x 修改 至多 一个字符会变成 y，那么我们称它与 y 几乎相等。

如果一个下标序列 seq 满足以下条件，我们称它是 合法的：

• 下标序列是 升序 的。
• 将 word1 中这些下标对应的字符 按顺序 连接，得到一个与 word2 几乎相等 的字符串。

请你返回一个长度为 word2.length 的数组，表示一个 字典序最小 的 合法 下标序列。如果不存在这样的序列，请你返回一个 空 数组。

注意，答案数组必须是字典序最小的下标数组，而 不是 由这些下标连接形成的字符串。

样例

输入：word1 = "vbcca", word2 = "abc"

输出：[0,1,2]

解释：

字典序最小的合法下标序列为 [0, 1, 2]：

将 word1[0] 变为 'a'。
word1[1] 已经是 'b'。
word1[2] 已经是 'c'。

输入：word1 = "bacdc", word2 = "abc"

输出：[1,2,4]

解释：

字典序最小的合法下标序列为 [1, 2, 4]：

word1[1] 已经是 'a'。
将 word1[2] 变为 'b'。
word1[4] 已经是 'c'。

输入：word1 = "aaaaaa", word2 = "aaabc"

输出：[]

解释：

没有合法的下标序列。

输入：word1 = "abc", word2 = "ab"

输出：[0,1]

限制

• 1 <= word2.length < word1.length <= 3 * 10^5
• word1 和 word2 只包含小写英文字母。

算法

(贪心，前后缀分解) $O(n)$

1. 从头开始匹配如果 $word1(i)$ 与 $word2(j)$ 发生了失配，假设我们可以快速判断出 $word1(i + 1, \dots, n - 1)$ 和 $word2(j + 1, \dots, m - 1)$ 是否可以完全匹配，则可以根据这个判断结果选择使用唯一的修改机会还是继续移动 $i$ 进行匹配。
2. 可以提前倒序预处理 $p(i)$，表示 $word1(i, \dots, n - 1)$ 可以完全匹配 $word2(p(i), \dots, m - 1)$。
3. 按照步骤 1 的思路进行匹配，并通过 $p(i)$ 进行判断。由于答案需要字典序最小，如果可以使用修改机会使得后缀可以完全匹配，则跳出循环，直接进行匹配输出答案。

时间复杂度

空间复杂度

C++ 代码

class Solution {
public:
    vector<int> validSequence(string word1, string word2) {
        const int n = word1.size(), m = word2.size();

        vector<int> p(n);
        for (int i = n - 1, j = m; i >= 0; i--) {
            if (j > 0 && word1[i] == word2[j - 1])
                --j;

            p[i] = j;
        }

        vector<int> ans;

        int i = 0, j = 0;
        while (i < n && j < m) {
            if (word1[i] == word2[j] || j == m - 1) {
                // 匹配，或者 word2 最后一个字符失配了，都可以继续
                ans.push_back(i);
                ++i; ++j;

                continue;
            }

            // 发生失配
            if (i == n - 1 || p[i + 1] > j + 1) {
                // word2 的后缀不能完全匹配，继续移动 i 进行尝试。
                ++i;

                continue;
            }

            // word2 的后缀可以完全匹配，结束循环
            ans.push_back(i);
            ++i; ++j;

            break; 
        }

        if (j < m && (i == n || p[i] > j))
            return {};

        while (i < n && j < m) {
            if (word1[i] == word2[j]) {
                ans.push_back(i);
                ++j;
            }

            ++i;
        }

        return ans;
    }
};