LeetCode 解題筆記：792. Number of Matching Subsequences

作者：王一哲
日期：2026年10月3日


LeetCode 題目連結：792. Number of Matching Subsequences

解題想法

中等難度題。題目給一個字串 $s$ 及一個字串陣列 $words$，要計算 $words$ 之中有幾個是 $s$ 的子序列 (subsecquence)。子序列是由 $s$ 刪除任意數量的字母，並且保持剩下的字母順序。由於這題的 $s$ 長度可達 $50000$，如果用雙層迴圈跑出 $s$ 所有的子序列會超時。我的作法是先用一個字典或陣列 $pos$，記錄 $s$ 之中每個字母的索引值，索引值由小到大排序。再寫一個檢測輸入的字串 $target$ 是否為 $s$ 子序列的函式 $check$，於函式中依序讀取 $target$ 的字母 $c$，用二分搜尋法從 $pos$ 對應到 $c$ 的資料中，搜尋是否有在前一個字母索引值 $pre$ 之後的字母 $c$，如果沒有就回傳 False；如果 $target$ 所有的字母都能被找到，回傳 True。

Python 程式碼

Runtime: 352 ms, beats 33.32%. Memory: 23.02 MB, beats 33.91%.

from bisect import bisect_left

class Solution:
    def numMatchingSubseq(self, s: str, words: list[str]) -> int:
        n = len(s)  # 長度
        # 各字母於 s 的索引值，用於二分搜尋法
        pos = [[] for _ in range(26)]
        for i in range(n):
            pos[ord(s[i]) - ord('a')].append(i)
        
        # 檢測 target 是否為 s 子序列的函式
        def check(target):
            pre = -1  # 前一個字母於 s 的索引值
            for c in target:
                arr = pos[ord(c) - ord('a')]  # 字母 c 於 s 的索引值
                j = bisect_left(arr, pre + 1)  # 找出大於等於 pre + 1 的索引值
                if j == len(arr):  # 沒找到，回傳 False
                    return False
                pre = arr[j]  # 更新 pre
            return True  # 都有找到，回傳 True
        
        # 檢測 words 之中的字串，計算答案
        ans = 0
        for word in words:
            if check(word):
                ans += 1
                
        return ans

Runtime: 282 ms, beats 57.13%. Memory: 23.22 MB, beats 16.90%.

from bisect import bisect_left

class Solution:
    def numMatchingSubseq(self, s: str, words: list[str]) -> int:
        n = len(s)  # 長度
        # 各字母於 s 的索引值，用於二分搜尋法
        pos = defaultdict(list)
        for i in range(n):
            pos[s[i]].append(i)
        
        # 檢測 target 是否為 s 子序列的函式
        def check(target):
            pre = -1  # 前一個字母於 s 的索引值
            for c in target:
                arr = pos[c]  # 字母 c 於 s 的索引值
                j = bisect_left(arr, pre + 1)  # 找出大於等於 pre + 1 的索引值
                if j == len(arr):  # 沒找到，回傳 False
                    return False
                pre = arr[j]  # 更新 pre
            return True  # 都有找到，回傳 True
        
        # 檢測 words 之中的字串，計算答案
        ans = 0
        for word in words:
            if check(word):
                ans += 1
                
        return ans

C++ 程式碼

Runtime: 62 ms, beats 77.80%. Memory: 59.39 MB, beats 34.29%.

class Solution {
private:
    vector<vector<int>> pos;  // 各字母於 s 的索引值，用於二分搜尋法
    
public:
    bool check(const string& target) {
        // 檢測 target 是否為 s 子序列的函式
        int pre = -1;  // 前一個字母於 s 的索引值
        for(char c : target) {
            int idx = c - 'a';
            auto it = lower_bound(pos[idx].begin(), pos[idx].end(), pre + 1);
            if (it == pos[idx].end()) {  // 沒找到，回傳 False
                return false;
            }
            pre = *it;  // 更新 pre
        }
        return true;  // 都有找到，回傳 True
    }
    
    int numMatchingSubseq(string s, vector<string>& words) {
        int n = (int)s.size();
        pos.assign(26, vector<int> (0));
        for(int i = 0; i < n; i++) {
            pos[s[i] - 'a'].push_back(i);
        }
        
        // 檢測 words 之中的字串，計算答案
        int ans = 0;
        for(auto word : words) {
            if (check(word)) {
                ans++;
            }
        }
        return ans;
    }
};

Runtime: 96 ms, beats 42.15%. Memory: 59.54 MB, beats 31.42%.

class Solution {
private:
    unordered_map<char, vector<int>> pos;  // 各字母於 s 的索引值，用於二分搜尋法
    
public:
    bool check(const string& target) {
        // 檢測 target 是否為 s 子序列的函式
        int pre = -1;  // 前一個字母於 s 的索引值
        for(char c : target) {
            auto it = lower_bound(pos[c].begin(), pos[c].end(), pre + 1);
            if (it == pos[c].end()) {  // 沒找到，回傳 False
                return false;
            }
            pre = *it;  // 更新 pre
        }
        return true;  // 都有找到，回傳 True
    }
    
    int numMatchingSubseq(string s, vector<string>& words) {
        int n = (int)s.size();
        pos.clear();
        for(int i = 0; i < n; i++) {
            pos[s[i]].push_back(i);
        }
        
        // 檢測 words 之中的字串，計算答案
        int ans = 0;
        for(auto word : words) {
            if (check(word)) {
                ans++;
            }
        }
        return ans;
    }
};