792 Number of Matching Subsequences

792. Number of Matching Subsequence​
1. Question
Given stringSand a dictionary of wordswords, find the number ofwords[i]that is a subsequence ofS.
1
Example :
2
​
3
Input: S = "abcde"
4
words = ["a", "bb", "acd", "ace"]
5
​
6
Output: 3
7
​
8
Explanation:
9
There are three words in words that are a subsequence of S: "a", "acd", "ace".
Copied!
Note:
All words inwordsandSwill only consists of lowercase letters.
The length ofSwill be in the range of[1, 50000].
The length ofwordswill be in the range of [1, 5000].
The length ofwords[i]will be in the range of[1, 50].
2. Implementation
(1) Brute Force
1
class Solution {
2
    public int numMatchingSubseq(String S, String[] words) {
3
        int res = 0;
4
​
5
        for (String word : words) {
6
            if (word.length() > S.length()) continue;
7
​
8
            if (isSubsequence(word, S)) {
9
                ++res;
10
            }
11
        }
12
        return res;
13
    }
14
​
15
    public boolean isSubsequence(String t, String s) {
16
        int tIndex = 0;
17
        for (int i = 0; i < s.length() && tIndex < t.length(); i++) {
18
            if (s.charAt(i) == t.charAt(tIndex)) {
19
                ++tIndex;
20
            }
21
        }
22
        return tIndex == t.length();
23
    }
24
}
Copied!
(2) HashMap + Queue
1
class Solution {
2
    public int numMatchingSubseq(String S, String[] words) {
3
        int res = 0;
4
​
5
        Map<Character, Queue<String>> map = new HashMap<>();
6
​
7
        for (char c : S.toCharArray()) {
8
            if (!map.containsKey(c)) {
9
                map.put(c, new LinkedList<>());
10
            }
11
        }
12
​
13
        for (String word : words) {
14
            if (word.length() > S.length()) continue;
15
​
16
            if (map.containsKey(word.charAt(0))) {
17
                map.get(word.charAt(0)).add(word);
18
            }
19
        }
20
​
21
        for (char c : S.toCharArray()) {
22
            Queue<String> queue = map.get(c);
23
​
24
            int size = queue.size();
25
​
26
            for (int i = 0; i < size; i++) {
27
                String curWord = queue.remove();
28
​
29
                if (curWord.length() == 1) {
30
                    ++res;
31
                }
32
                else if (map.containsKey(curWord.charAt(1))) {
33
                    map.get(curWord.charAt(1)).add(curWord.substring(1));
34
                }
35
            }
36
        }
37
        return res;
38
    }
39
}
Copied!
(3) Memoization
1
class Solution {
2
    public int numMatchingSubseq(String S, String[] words) {
3
        int res = 0;
4
​
5
        Map<String, Boolean> cache = new HashMap<>();
6
​
7
        for (String word : words) {
8
            if (word.length() > S.length()) continue;
9
​
10
            if (isSubsequence(word, S, cache)) {
11
                ++res;
12
            }
13
        }
14
        return res;
15
    }
16
​
17
    public boolean isSubsequence(String word, String S, Map<String, Boolean> cache) {
18
        if (cache.get(word) != null) {
19
            return cache.get(word);
20
        }
21
​
22
        int index = -1;
23
        for (char c : word.toCharArray()) {
24
            index = S.indexOf(c, index + 1);
25
​
26
            if (index == -1) {
27
                cache.put(word, false);
28
                return false;
29
            }
30
        }
31
        cache.put(word, true);
32
        return true;
33
    }
34
}
Copied!
3. Time & Space Complexity
Brute Force: 时间复杂度O(nL), n为word的个数，L为S的长度， 空间复杂度O(1)
HashMap + Queue: 时间复杂度O(nL), 空间复杂度O(n)
Memoization: 时间复杂度O(nL), 空间复杂度O(n)

777 Swap Adjacent in LR String

460 LFU Cache

Last modified 2yr ago

Copy link

Contents

792. Number of Matching Subsequence

1. Question

2. Implementation

3. Time & Space Complexity

792. Number of Matching Subsequence​

1. Question

2. Implementation

3. Time & Space Complexity

792. Number of Matching Subsequence