LeetCode 题解工作台
字典序最小的合法序列
给你两个字符串 word1 和 word2 。 如果一个字符串 x 修改 至多 一个字符会变成 y ，那么我们称它与 y 几乎相等 。 如果一个下标序列 seq 满足以下条件，我们称它是 合法的 ： 下标序列是 升序 的 。 将 word1 中这些下标对应的字符 按顺序 连接，得到一个与 word2…
4
题型
0
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你两个字符串 word1 和 word2 。
如果一个字符串 x 修改 至多 一个字符会变成 y ，那么我们称它与 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 * 105word1和word2只包含小写英文字母。
解题思路
方法一
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on building dp[i] for each suffix and iterating with two pointers, potentially O(word1.length * word2.length). Space complexity is dominated by dp array and auxiliary arrays for character positions. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check if the candidate correctly defines the DP state for suffix matching.
- question_mark
Listen for a greedy step combined with DP to ensure lexicographic minimality.
- question_mark
Verify handling of almost-equal condition and empty sequence returns.
常见陷阱
外企场景- error
Ignoring the almost-equal rule when choosing characters from word1.
- error
Not maintaining lexicographic order while constructing the result.
- error
Inefficient DP that recomputes suffix matches repeatedly.
进阶变体
外企场景- arrow_right_alt
Compute the lexicographically largest valid sequence instead of smallest.
- arrow_right_alt
Allow up to k character changes in the almost-equal definition.
- arrow_right_alt
Return all valid sequences rather than only the minimal one.