Leetcode 792. 匹配子序列的单词数

Posted on In ,

题目描述

给定字符串 s 和字符串数组 words, 返回  words[i] 中是s的子序列的单词个数 。

字符串的 子序列 是从原始字符串中生成的新字符串，可以从中删去一些字符(可以是none)，而不改变其余字符的相对顺序。

  • 例如， “ace” 是 “abcde” 的子序列。

 

示例 1: 

输入: s = "abcde", words = ["a","bb","acd","ace"]
输出: 3
解释: 有三个是 s 的子序列的单词: "a", "acd", "ace"。

Example 2: 

输入: s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]
输出: 2

 

提示:

  • 1 <= s.length <= 5 * 104
  • 1 <= words.length <= 5000
  • 1 <= words[i].length <= 50
  • words[i]和 s 都只由小写字母组成。
​​​​

解答

很容易想到将words整理，并且每看一个c in s就将所有匹配到的word的ptr++。

一开始想到用排序的方法整理，那样每次都需要nlogn的时间，并且找到匹配的word还要logn的时间。

考虑到c和word都是离散的，直接用个map存就可以了。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int numMatchingSubseq(string s, vector<string>& words) {
        unordered_map<char,queue<pair<int,int>>> map;
        // In the pair, first is the order of word in words,
        // second is the location of ptr in the word

        for (int i=0;i<words.size();i++){
            map[words[i][0]].push(make_pair(i,0));
        }
        int ans=0;
        for (auto c:s){
            int size=map[c].size();
            while(size--){
                auto ptr=map[c].front();
                map[c].pop();
                if (ptr.second==(words[ptr.first].size()-1)){
                    ans++;
                }
                else{
                    map[words[ptr.first][ptr.second+1]].emplace(make_pair(ptr.first,ptr.second+1));
                }
            }
        }
        return ans;
    }
};

Complexity

  • Time: \(O(s.size+\sum words[i].size)\)
  • Space: \(O(words.size)\)

题外话

  • C++ STL中的queue不支持iterator，如有需求请使用deque。