792 Number of Matching Subsequences

792. Number of Matching Subsequence

1. Question

Given stringSand a dictionary of wordswords, find the number ofwords[i]that is a subsequence ofS.

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

class Solution {
    public int numMatchingSubseq(String S, String[] words) {
        int res = 0;

        for (String word : words) {
            if (word.length() > S.length()) continue;

            if (isSubsequence(word, S)) {
                ++res;
            }
        }
        return res;
    }

    public boolean isSubsequence(String t, String s) {
        int tIndex = 0;
        for (int i = 0; i < s.length() && tIndex < t.length(); i++) {
            if (s.charAt(i) == t.charAt(tIndex)) {
                ++tIndex;
            }
        }
        return tIndex == t.length();
    }
}

(2) HashMap + Queue

class Solution {
    public int numMatchingSubseq(String S, String[] words) {
        int res = 0;

        Map<Character, Queue<String>> map = new HashMap<>();

        for (char c : S.toCharArray()) {
            if (!map.containsKey(c)) {
                map.put(c, new LinkedList<>());
            }
        }

        for (String word : words) {
            if (word.length() > S.length()) continue;

            if (map.containsKey(word.charAt(0))) {
                map.get(word.charAt(0)).add(word);
            }
        }

        for (char c : S.toCharArray()) {
            Queue<String> queue = map.get(c);

            int size = queue.size();

            for (int i = 0; i < size; i++) {
                String curWord = queue.remove();

                if (curWord.length() == 1) {
                    ++res;
                }
                else if (map.containsKey(curWord.charAt(1))) {
                    map.get(curWord.charAt(1)).add(curWord.substring(1));
                }
            }
        }
        return res;
    }
}

(3) Memoization

class Solution {
    public int numMatchingSubseq(String S, String[] words) {
        int res = 0;

        Map<String, Boolean> cache = new HashMap<>();

        for (String word : words) {
            if (word.length() > S.length()) continue;

            if (isSubsequence(word, S, cache)) {
                ++res;
            }
        }
        return res;
    }

    public boolean isSubsequence(String word, String S, Map<String, Boolean> cache) {
        if (cache.get(word) != null) {
            return cache.get(word);
        }

        int index = -1;
        for (char c : word.toCharArray()) {
            index = S.indexOf(c, index + 1);

            if (index == -1) {
                cache.put(word, false);
                return false;
            }
        }
        cache.put(word, true);
        return true;
    }
}

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)