Google
792 Number of Matching Subsequences

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)