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

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;
    }
}

// OJ: https://leetcode.com/problems/number-of-matching-subsequences/
// Time: O(S + NWlogS)
// Space: O(S)
class Solution {
public:
    int numMatchingSubseq(string s, vector<string>& A) {
        vector<int> index[26];
        for (int i = 0; i < s.size(); ++i) index[s[i] - 'a'].push_back(i);
        int ans = 0;
        for (auto &w : A) {
            int i = 0, j = 0;
            for (; i < w.size(); ++i) {
                auto &v = index[w[i] - 'a'];
                auto it = lower_bound(begin(v), end(v), j);
                if (it == end(v)) break;
                j = *it + 1;
            }
            ans += i == w.size();
        }
        return ans;
    }
};

class Solution(object):
    def numMatchingSubseq(self, S, words):
        """
        :type S: str
        :type words: List[str]
        :rtype: int
        """
        m = dict()
        def isMatch(word, d):
            if word in m:
                return m[word]
            prev = -1
            for w in word:
                i = bisect.bisect_left(d[w], prev + 1)
                if i == len(d[w]):
                    return 0
                prev = d[w][i]
            m[word] = 1
            return 1
        
        d = collections.defaultdict(list)
        for i, s in enumerate(S):
            d[s].append(i)
        ans = [isMatch(word, d) for word in words]
        return sum(ans)

792 - Number of Matching Subsequences

792. Number of Matching Subsequences

Level

Description

Solution

All Problems

All Solutions