class Solution {
public:
int appendCharacters(string s, string t) {
}
};
2486. 追加字符以获得子序列
给你两个仅由小写英文字母组成的字符串 s 和 t 。
现在需要通过向 s 末尾追加字符的方式使 t 变成 s 的一个 子序列 ，返回需要追加的最少字符数。
子序列是一个可以由其他字符串删除部分（或不删除）字符但不改变剩下字符顺序得到的字符串。
示例 1：
输入：s = "coaching", t = "coding"
输出：4
解释：向 s 末尾追加字符串 "ding" ，s = "coachingding" 。
现在，t 是 s ("coachingding") 的一个子序列。
可以证明向 s 末尾追加任何 3 个字符都无法使 t 成为 s 的一个子序列。
示例 2：
输入：s = "abcde", t = "a"
输出：0
解释：t 已经是 s ("abcde") 的一个子序列。
示例 3：
输入：s = "z", t = "abcde"
输出：5
解释：向 s 末尾追加字符串 "abcde" ，s = "zabcde" 。
现在，t 是 s ("zabcde") 的一个子序列。
可以证明向 s 末尾追加任何 4 个字符都无法使 t 成为 s 的一个子序列。
提示：
1 <= s.length, t.length <= 105s 和 t 仅由小写英文字母组成原站题解
golang 解法, 执行用时: 8 ms, 内存消耗: 5.4 MB, 提交时间: 2022-12-01 09:59:13
func appendCharacters(s, t string) int {
j, m := 0, len(t)
for _, c := range s {
if byte(c) == t[j] { // s 的字符肯定匹配的是 t 的前缀
j++
if j == m {
return 0
}
}
}
return m - j
}
python3 解法, 执行用时: 60 ms, 内存消耗: 15.7 MB, 提交时间: 2022-12-01 09:58:55
class Solution:
def appendCharacters(self, s: str, t: str) -> int:
j, m = 0, len(t)
for c in s:
if c == t[j]:
j += 1
if j == m: return 0
return m - j
golang 解法, 执行用时: 8 ms, 内存消耗: 5.4 MB, 提交时间: 2022-12-01 09:58:42
func appendCharacters(s, t string) int {
i, n := 0, len(s)
for j := range t {
for i < n && s[i] != t[j] {
i++
}
if i == n {
return len(t) - j
}
i++
}
return 0
}
python3 解法, 执行用时: 72 ms, 内存消耗: 15.6 MB, 提交时间: 2022-12-01 09:58:29
'''
贪心，双指针遍历 s 和 t，t[j] 应匹配 i 尽量小（但大于上一个的匹配的位置）的 s[i]。
'''
class Solution:
def appendCharacters(self, s: str, t: str) -> int:
i, n = 0, len(s)
for j, c in enumerate(t):
while i < n and s[i] != t[j]: i += 1
if i == n: return len(t) - j
i += 1
return 0