匹配子序列的单词数 图解题解

这道题到底在问什么

输入

s="abcde", words=["a","bb","acd","ace"]

输出

3（a、acd、ace 是子序列；bb 不是）

最优解：一步一步想明白

1. 3记住「字符分桶记下标 → 每个字符二分找第一个比 cur 大的位置 → cur 往后跳」,下面每帧都在套它。
2. 4先一遍扫 s="abcde"，把每个字符出现的位置记进桶里:a 在下标 0、b 在 1、c 在 2、d 在 3、e 在 4。这张桶表建一次、所有单词共用,这正是它比每词重扫 s 省时的地方。
3. 5轮到单词 "a"。游标 cur 从 −1 开始,表示还没用掉 s 里任何位置。接下来逐个字符,在它的桶里找第一个比 cur 大的下标。
4. 6匹配 'a':在它的桶 [0] 里,第一个比 cur=-1 大的下标是 0。把 cur 跳到 0,表示用 s 第 0 位的 'a' 接上了。s 上高亮往后推进。
5. 7"a" 的每个字符都在 s 里按顺序找到了落点(0),它是 s 的子序列,答案加一,现在是 1。
6. 8轮到单词 "bb"。游标 cur 从 −1 开始,表示还没用掉 s 里任何位置。接下来逐个字符,在它的桶里找第一个比 cur 大的下标。
7. 9匹配 'b':在它的桶 [1] 里,第一个比 cur=-1 大的下标是 1。把 cur 跳到 1,表示用 s 第 1 位的 'b' 接上了。s 上高亮往后推进。
8. 10要匹配 'b',去它的桶 [1] 里找第一个比当前 cur=1 大的下标。桶里最大的也才 1，没有比 1 更靠后的了。这个字符接不上,单词 "bb" 失败。
9. 11"bb" 没能走完,不是子序列,答案保持 1。注意它失败不是因为缺字符种类,而是同一个字符在 s 里不够用、排不出递增的位置。
10. 12轮到单词 "acd"。游标 cur 从 −1 开始,表示还没用掉 s 里任何位置。接下来逐个字符,在它的桶里找第一个比 cur 大的下标。
11. 13匹配 'a':在它的桶 [0] 里,第一个比 cur=-1 大的下标是 0。把 cur 跳到 0,表示用 s 第 0 位的 'a' 接上了。s 上高亮往后推进。
12. 14匹配 'c':在它的桶 [2] 里,第一个比 cur=0 大的下标是 2。把 cur 跳到 2,表示用 s 第 2 位的 'c' 接上了。s 上高亮往后推进。
13. 15匹配 'd':在它的桶 [3] 里,第一个比 cur=2 大的下标是 3。把 cur 跳到 3,表示用 s 第 3 位的 'd' 接上了。s 上高亮往后推进。
14. 16"acd" 的每个字符都在 s 里按顺序找到了落点(0 → 2 → 3),它是 s 的子序列,答案加一,现在是 2。
15. 17轮到单词 "ace"。游标 cur 从 −1 开始,表示还没用掉 s 里任何位置。接下来逐个字符,在它的桶里找第一个比 cur 大的下标。
16. 18匹配 'a':在它的桶 [0] 里,第一个比 cur=-1 大的下标是 0。把 cur 跳到 0,表示用 s 第 0 位的 'a' 接上了。s 上高亮往后推进。
17. 19匹配 'c':在它的桶 [2] 里,第一个比 cur=0 大的下标是 2。把 cur 跳到 2,表示用 s 第 2 位的 'c' 接上了。s 上高亮往后推进。
18. 20匹配 'e':在它的桶 [4] 里,第一个比 cur=2 大的下标是 4。把 cur 跳到 4,表示用 s 第 4 位的 'e' 接上了。s 上高亮往后推进。
19. 21"ace" 的每个字符都在 s 里按顺序找到了落点(0 → 2 → 4),它是 s 的子序列,答案加一,现在是 3。
20. 22四个单词判完:a、acd、ace 是子序列,bb 不是,共 3 个。回头看,我们只建了一次位置桶,每个单词靠「在桶里二分找第一个比 cur 大的下标」一路往后跳,没有为每个词重新扫一遍 s。

⚠️ 容易写错的地方

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

from typing import List
from bisect import bisect_right
class Solution:
    def numMatchingSubseq(self, s: str, words: List[str]) -> int:
        pos = [[] for _ in range(26)]
        for i, ch in enumerate(s):
            pos[ord(ch) - 97].append(i)
        ans = 0
        for w in words:
            cur = -1
            ok = True
            for ch in w:
                arr = pos[ord(ch) - 97]
                j = bisect_right(arr, cur)
                if j == len(arr):
                    ok = False
                    break
                cur = arr[j]
            ans += ok
        return ans

#include <algorithm>
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
    int numMatchingSubseq(string s, vector<string>& words) {
        vector<vector<int>> pos(26);
        for (int i = 0; i < (int)s.size(); ++i) pos[s[i]-'a'].push_back(i);
        int ans = 0;
        for (auto &w : words) {
            int cur = -1;
            bool ok = true;
            for (char c : w) {
                auto &arr = pos[c-'a'];
                auto it = upper_bound(arr.begin(), arr.end(), cur);
                if (it == arr.end()) { ok = false; break; }
                cur = *it;
            }
            if (ok) ans++;
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public int numMatchingSubseq(String s, String[] words) {
        List<Integer>[] pos = new ArrayList[26];
        for (int i = 0; i < 26; i++) pos[i] = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) pos[s.charAt(i) - 'a'].add(i);
        int ans = 0;
        for (String w : words) {
            int cur = -1;
            boolean ok = true;
            for (char c : w.toCharArray()) {
                List<Integer> arr = pos[c - 'a'];
                int j = Collections.binarySearch(arr, cur + 1);
                if (j < 0) j = -j - 1;
                if (j == arr.size()) { ok = false; break; }
                cur = arr.get(j);
            }
            if (ok) ans++;
        }
        return ans;
    }
}

复杂度

面试官可能追问