Formatted question description:

792. Number of Matching Subsequences




Given string S and a dictionary of words words, find the number of words[i] that is a subsequence of S.



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”.


  • All words in words and S 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].


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) {
                int wordLength = node.word.length();
                if (node.index == wordLength)
                    heads[node.word.charAt(node.index) - 'a'].add(node);
        return count;

class Node {
    String word;
    int index;

    public Node(String word, int index) {
        this.word = word;
        this.index = index;

All Problems

All Solutions