class Solution {
public:
vector<int> validSequence(string word1, string word2) {
}
};
3302. 字典序最小的合法序列
给你两个字符串 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 只包含小写英文字母。相似题目
原站题解
cpp 解法, 执行用时: 170 ms, 内存消耗: 105.2 MB, 提交时间: 2024-10-18 09:15:13
class Solution {
public:
vector<int> validSequence(string s, string t) {
int n = s.length(), m = t.length();
vector<int> suf(n + 1);
suf[n] = m;
for (int i = n - 1, j = m - 1; i >= 0; i--) {
if (j >= 0 && s[i] == t[j]) {
j--;
}
suf[i] = j + 1;
}
vector<int> ans(m);
bool changed = false; // 是否修改过
for (int i = 0, j = 0; i < n; i++) {
if (s[i] == t[j] || !changed && suf[i + 1] <= j + 1) {
if (s[i] != t[j]) {
changed = true;
}
ans[j++] = i;
if (j == m) {
return ans;
}
}
}
return {};
}
};
java 解法, 执行用时: 36 ms, 内存消耗: 73 MB, 提交时间: 2024-10-18 09:15:01
class Solution {
public int[] validSequence(String word1, String word2) {
char[] s = word1.toCharArray();
char[] t = word2.toCharArray();
int n = s.length;
int m = t.length;
int[] suf = new int[n + 1];
suf[n] = m;
int j = m - 1;
for (int i = n - 1; i >= 0; i--) {
if (j >= 0 && s[i] == t[j]) {
j--;
}
suf[i] = j + 1;
}
int[] ans = new int[m];
boolean changed = false; // 是否修改过
j = 0;
for (int i = 0; i < n; i++) {
if (s[i] == t[j] || !changed && suf[i + 1] <= j + 1) {
if (s[i] != t[j]) {
changed = true;
}
ans[j++] = i;
if (j == m) {
return ans;
}
}
}
return new int[]{};
}
}
golang 解法, 执行用时: 122 ms, 内存消耗: 12.2 MB, 提交时间: 2024-10-18 09:14:46
func validSequence(s, t string) []int {
n, m := len(s), len(t)
suf := make([]int, n+1)
suf[n] = m
for i, j := n-1, m-1; i >= 0; i-- {
if j >= 0 && s[i] == t[j] {
j--
}
suf[i] = j + 1
}
ans := make([]int, m)
changed := false // 是否修改过
j := 0
for i := range s {
if s[i] == t[j] || !changed && suf[i+1] <= j+1 {
if s[i] != t[j] {
changed = true
}
ans[j] = i
j++
if j == m {
return ans
}
}
}
return nil
}
python3 解法, 执行用时: 549 ms, 内存消耗: 47.9 MB, 提交时间: 2024-10-18 09:14:32
class Solution:
def validSequence(self, s: str, t: str) -> List[int]:
n, m = len(s), len(t)
suf = [0] * (n + 1)
suf[n] = m
j = m - 1
for i in range(n - 1, -1, -1):
if j >= 0 and s[i] == t[j]:
j -= 1
suf[i] = j + 1
ans = []
changed = False # 是否修改过
j = 0
for i, c in enumerate(s):
if c == t[j] or not changed and suf[i + 1] <= j + 1:
if c != t[j]:
changed = True
ans.append(i)
j += 1
if j == m:
return ans
return []