808. Number Of Matching Subsequences¶

Difficulty: Medium

808. Number of Matching Subsequences

Medium

Given a string s and an array of strings words, return the number of words[i] that is a subsequence of s.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

For example, "ace" is a subsequence of "abcde".

Example 1:

Input: s = "abcde", words = ["a","bb","acd","ace"]
Output: 3
Explanation: There are three strings in words that are a subsequence of s: "a", "acd", "ace".

Example 2:

Input: s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]
Output: 2

Constraints:

1 <= s.length <= 5 * 10⁴
1 <= words.length <= 5000
1 <= words[i].length <= 50
s and words[i] consist of only lowercase English letters.

Solution¶

class Solution {
    private HashMap<Character, TreeSet<Integer>> map;
    public int numMatchingSubseq(String s, String[] words) {
        map = new HashMap<>();
        preProcess(s);
        int count = 0;
        for (int i = 0; i < words.length; i++) {
            if (check(words[i])) 
                count++;
        }
        return count;
    }
    private boolean check(String s) {
        int n = s.length();
        int ind = -1;
        for (int i = 0; i < n; i++) {
            char current = s.charAt(i);
            if (!map.containsKey(current)) 
                return false;
            TreeSet<Integer> currChar = map.get(current);
            Integer next = currChar.higher(ind);
            if (next == null) 
                return false;
            ind = next;
        }
        return true;
    }
    private void preProcess(String s) {
        int n = s.length();
        for (int i = 0; i < n; i++) {
            char current = s.charAt(i);
            if (!map.containsKey(current))
                map.put(current, new TreeSet<>());
            map.get(current).add(i);
        }
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here