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
wordsandSwill only consists of lowercase letters. - The length of
Swill be in the range of[1, 50000]. - The length of
wordswill 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;
}
}