Medium

题目描述

给你两个仅由小写英文字母组成的字符串 s 和 t。

返回需要追加到 s 末尾的最少字符数，使得 t 成为 s 的子序列。

子序列是一个可以通过删除某些字符而不改变剩余字符顺序从另一个字符串派生出来的字符串。

示例 1：

输入：s = "coaching", t = "coding"
输出：4
解释：将字符 "ding" 追加到 s 的末尾，使得 s = "coachingding"。
现在，t 是 s 的子序列 ("coachingding")。
可以证明，将任何 3 个字符追加到 s 的末尾都无法使 t 成为子序列。

示例 2：

输入：s = "abcde", t = "a"
输出：0
解释：t 已经是 s 的子序列 ("abcde")。

示例 3：

输入：s = "z", t = "abcde"
输出：5
解释：将字符 "abcde" 追加到 s 的末尾，使得 s = "zabcde"。
现在，t 是 s 的子序列 ("zabcde")。
可以证明，将任何 4 个字符追加到 s 的末尾都无法使 t 成为子序列。

约束条件：

  • 1 <= s.length, t.length <= 10^5
  • s 和 t 仅由小写英文字母组成

解题思路

这道题的核心思想是找到字符串 t 中已经作为字符串 s 子序列存在的最长前缀，剩余部分就是需要追加到 s 末尾的字符。

解题思路：

使用双指针贪心策略是最直接有效的方法。我们用两个指针 i 和 j 分别指向字符串 s 和 t 的当前位置：

  1. 初始化两个指针都为 0
  2. 遍历字符串 s，对于每个字符：
    • 如果 s[i] 等于 t[j]，说明找到了 t 中的一个字符，将 j 向前移动
    • 无论是否匹配，都将 i 向前移动
  3. 遍历结束后，j 的值表示 t 中已经匹配的字符数量
  4. 返回 t.length - j，即未匹配的字符数量

这个贪心策略是正确的，因为我们总是尽可能地匹配 t 中的字符。由于子序列要求保持字符顺序，一旦在 s 中找到 t[j] 对应的字符，就应该立即匹配，这样能保证找到最长的已存在前缀。

时间复杂度： O(n)，其中 n 是字符串 s 的长度 空间复杂度： O(1)，只使用了常数个额外变量

代码实现

class Solution {
public:
    int appendCharacters(string s, string t) {
        int j = 0;
        for (int i = 0; i < s.length() && j < t.length(); i++) {
            if (s[i] == t[j]) {
                j++;
            }
        }
        return t.length() - j;
    }
};

class Solution:
    def appendCharacters(self, s: str, t: str) -> int:
        j = 0
        for i in range(len(s)):
            if j < len(t) and s[i] == t[j]:
                j += 1
        return len(t) - j

public class Solution {
    public int AppendCharacters(string s, string t) {
        int j = 0;
        for (int i = 0; i < s.Length && j < t.Length; i++) {
            if (s[i] == t[j]) {
                j++;
            }
        }
        return t.Length - j;
    }
}

var appendCharacters = function(s, t) {
    let j = 0;
    for (let i = 0; i < s.length && j < t.length; i++) {
        if (s[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)n 为字符串 s 的长度，需要遍历一次字符串 s
空间复杂度O(1)只使用了常数个额外变量

相关题目