Formatted question description: https://leetcode.ca/all/792.html
792. Number of Matching Subsequences
Level
Medium
Description
Given string S
and a dictionary of words words
, find the number of words[i]
that is a subsequence of S
.
Example:
Input:
S = “abcde”
words = [“a”, “bb”, “acd”, “ace”]
Output: 3
Explanation: There are three words in words that are a subsequence of S: “a”, “acd”, “ace”.
Note:
- All words in
words
andS
will only consists of lowercase letters. - The length of
S
will be in the range of[1, 50000]
. - The length of
words
will be in the range of[1, 5000]
. - The length of
words[i]
will be in the range of[1, 50]
.
Solution
One solution is to check whether each word
in words
is a subsequence of S
, and count the number of subsequences, which is quite time-consuming since S
is looped over many times.
A better solution is to maintain buckets for each letter. For each word
in words
, for each letter, store the following letters in the buckets. If the end of word
is reached, add the counter by 1.
class Solution {
public int numMatchingSubseq(String S, String[] words) {
int count = 0;
ArrayList<Node>[] heads = new ArrayList[26];
for (int i = 0; i < 26; i++)
heads[i] = new ArrayList<Node>();
for (String word : words)
heads[word.charAt(0) - 'a'].add(new Node(word, 0));
char[] array = S.toCharArray();
for (char c : array) {
ArrayList<Node> oldBucket = heads[c - 'a'];
heads[c - 'a'] = new ArrayList<Node>();
for (Node node : oldBucket) {
node.index++;
int wordLength = node.word.length();
if (node.index == wordLength)
count++;
else
heads[node.word.charAt(node.index) - 'a'].add(node);
}
oldBucket.clear();
}
return count;
}
}
class Node {
String word;
int index;
public Node(String word, int index) {
this.word = word;
this.index = index;
}
}