追加字符以获得子序列

难度: Medium

给你两个仅由小写英文字母组成的字符串 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 <= 10⁵
s 和 t 仅由小写英文字母组成

Submission

运行时间: 40 ms

内存: 17.1 MB

class Solution:
    def appendCharacters(self, s: str, t: str) -> int:
        cur_t, t_len = 0, len(t)
        for ch in s:
            if ch == t[cur_t]:
                cur_t += 1
                # Early return
                if cur_t == t_len:
                    return 0
        return len(t) - cur_t

Explain

题解的核心思想是通过一个指针来遍历字符串t，同时遍历字符串s。对于s中的每一个字符，如果它与t中当前指针所指向的字符相同，则移动t的指针到下一个字符。这一过程继续，直到s被完全遍历或者t的指针移动到字符串t的末尾。如果在遍历完s后，t的指针已经到达t的末尾，说明t已经是s的子序列，此时无需追加任何字符。否则，需要追加的字符数就是t的剩余部分的长度，即len(t) - cur_t。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def appendCharacters(self, s: str, t: str) -> int:
        # 初始化指向t的当前索引和t的总长度
        cur_t, t_len = 0, len(t)
        # 遍历s中的每个字符
        for ch in s:
            # 如果当前s的字符与t中对应的字符相同
            if ch == t[cur_t]:
                cur_t += 1  # 移动t的指针
                # 如果t的所有字符都已经匹配完毕
                if cur_t == t_len:
                    return 0  # t已经是s的子序列，不需追加字符
        # 返回需要追加的字符数量，即t未被匹配的剩余部分
        return len(t) - cur_t

Explore

该方法仅在t的字符顺序与s中的部分字符顺序一致时有效。如果t的字符虽然在s中出现过，但顺序不同，那么这种方法不足以将t转换为s的子序列。例如，如果t是'abc'而s是'cba'，尽管t的所有字符都在s中，但由于顺序不同，无法通过简单地追加字符来使t成为s的子序列。因此，这种方法依赖于t的字符在s中的相对位置和顺序。

单次遍历s通常足够找到尽可能多的与t相匹配的字符，因为我们在遍历s的过程中逐步移动t的指针，并尽量匹配每一个字符。但这种方法假设了t中的字符在s中出现的顺序是一致的。如果t的字符在s中多次出现但顺序不同，单次遍历可能无法捕捉所有的匹配可能性。所以，这种方法最适用于t的字符顺序与s中字符的出现顺序相匹配的场景。

如果t是空字符串，根据题解的逻辑，初始化时't_len'将为0，因此在for循环中不会执行任何匹配操作，'cur_t'始终为0，最终返回0。因此，此逻辑正确处理了t为空字符串的情况，符合预期结果，即t已经是s的子序列，不需要追加任何字符。

代码实现确实跳过了与t当前指针所指向字符不匹配的s中的字符。这个策略基于假设t中的字符必须按照特定的顺序出现在s中，而不考虑s中字符的多次出现可能带来的多种匹配序列。这种方法在t的字符顺序与s中相应字符顺序严格匹配时最有效。如果存在多种顺序的匹配可能性，该策略可能不会找到所有可能的子序列，但对于确定t是否为s的子序列来说是足够的。