追加字符以获得子序列 图解题解

这道题到底在问什么

输入

s = "coaching", t = "coding"

输出

4

输入

s = "abcde", t = "a"

输出

0

输入

s = "z", t = "abcde"

输出

5

最优解：一步一步想明白

1. 3记牢这一句:一个指针 j 顺着 t 走,在 s 里从左到右能对上就前进,对不上就跳过;s 扫完 j 停在哪,答案就是 t 的长度减去 j。下面每一帧都在套这句话。
2. 4先把两个串摆好。上面这一排是 s,coaching,一共 8 个字符,我们要在它里面从左到右顺序匹配。右边这一列是目标串 t,coding,共 6 个字符,谁被匹配到就打勾。现在还一个都没开始,匹配进度 j 是 0,高亮的是 t 的第一个字符 c,那是我们最先要在 s 里找的。
3. 5指针就位。i 指向 s 的第 0 个字符,也就是 c;j 指向 t 的第 0 个字符,也是 c。接下来的规则很简单,拿 s[i] 和 t[j] 比:相等就说明 t 的这个字符在 s 里对上了,j 前进;不相等就只把 s 往后挪,j 原地不动。
4. 6扫到 s 的第 0个字符 c。现在 j 是 0,要找的 t[0] 是 c。把这两个放一起比一比:c 和 c 一样吗?
5. 7一样!c 正好是要找的 t 字符,命中。把 s 的这一格标绿,j 前进到 1,下一个要在 s 里找的目标变成 t[1] 等于 o。已经顺次对上 1 个了。
6. 8扫到 s 的第 1个字符 o。现在 j 是 1,要找的 t[1] 是 o。把这两个放一起比一比:o 和 o 一样吗?
7. 9一样!o 正好是要找的 t 字符,命中。把 s 的这一格标绿,j 前进到 2,下一个要在 s 里找的目标变成 t[2] 等于 d。已经顺次对上 2 个了。
8. 10扫到 s 的第 2个字符 a。现在 j 是 2,要找的 t[2] 是 d。把这两个放一起比一比:a 和 d 一样吗?
9. 11不一样。a 不是当前要找的 d,这个字符对匹配没用,直接跳过。注意 j 一点不动,还是 2,我们只是把 s 往后挪一格继续看。要找的目标依旧是 t[2] 等于 d。
10. 12扫到 s 的第 3个字符 c。现在 j 是 2,要找的 t[2] 是 d。把这两个放一起比一比:c 和 d 一样吗?
11. 13不一样。c 不是当前要找的 d,这个字符对匹配没用,直接跳过。注意 j 一点不动,还是 2,我们只是把 s 往后挪一格继续看。要找的目标依旧是 t[2] 等于 d。
12. 14扫到 s 的第 4个字符 h。现在 j 是 2,要找的 t[2] 是 d。把这两个放一起比一比:h 和 d 一样吗?
13. 15不一样。h 不是当前要找的 d,这个字符对匹配没用,直接跳过。注意 j 一点不动,还是 2,我们只是把 s 往后挪一格继续看。要找的目标依旧是 t[2] 等于 d。
14. 16扫到 s 的第 5个字符 i。现在 j 是 2,要找的 t[2] 是 d。把这两个放一起比一比:i 和 d 一样吗?
15. 17不一样。i 不是当前要找的 d,这个字符对匹配没用,直接跳过。注意 j 一点不动,还是 2,我们只是把 s 往后挪一格继续看。要找的目标依旧是 t[2] 等于 d。
16. 18扫到 s 的第 6个字符 n。现在 j 是 2,要找的 t[2] 是 d。把这两个放一起比一比:n 和 d 一样吗?
17. 19不一样。n 不是当前要找的 d,这个字符对匹配没用,直接跳过。注意 j 一点不动,还是 2,我们只是把 s 往后挪一格继续看。要找的目标依旧是 t[2] 等于 d。
18. 20扫到 s 的第 7个字符 g。现在 j 是 2,要找的 t[2] 是 d。把这两个放一起比一比:g 和 d 一样吗?
19. 21不一样。g 不是当前要找的 d,这个字符对匹配没用,直接跳过。注意 j 一点不动,还是 2,我们只是把 s 往后挪一格继续看。要找的目标依旧是 t[2] 等于 d。
20. 22s 的 8 个字符全部扫完了。回头看 j,它停在 2。这说明 t 的前 2 个字符,也就是 co,已经能在 s 里按顺序找到(看那两个绿格)。可是 j 没能走到底,t 后面还剩字符没匹配上。
21. 23看看 t 里没打勾的部分:ding,一共 4 个字符。它们在 s 里已经没有机会再顺序补齐了,因为 s 已经扫到头。想让 t 成为子序列,只能把这 ding 原样接到 s 的末尾。
22. 24答案出来了。t 的长度是 6,已经顺序匹配上 2 个,还差 6 减 2 等于 4 个。这 4 就是要往 s 末尾追加的最少字符数,追加后 s 变成 coachingding,t 就成了它的子序列。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def appendCharacters(self, s: str, t: str) -> int:
        n, j = len(t), 0
        for c in s:
            if j < n and c == t[j]:
                j += 1
        return n - j

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int appendCharacters(string s, string t) {
        int n = t.length(), j = 0;
        for (int i = 0; i < s.size() && j < n; ++i) {
            if (s[i] == t[j]) {
                ++j;
            }
        }
        return n - j;
    }
};

import java.util.*;
class Solution {
    public int appendCharacters(String s, String t) {
        int n = t.length(), j = 0;
        for (int i = 0; i < s.length() && j < n; ++i) {
            if (s.charAt(i) == t.charAt(j)) {
                ++j;
            }
        }
        return n - j;
    }
}

复杂度

面试官可能追问