392. Is Subsequence & 792. Number of Matching Subsequences

392. Is Subsequence

Given two strings s and t, return true if s is a subsequence of t, or false otherwise.

Example 1:

Input: s = "abc", t = "ahbgdc"
Output: true

Example 2:

Input: s = "axc", t = "ahbgdc"
Output: false

Constraints:

• 0 <= s.length <= 100

• 0 <= t.length <= 104

• s and t consist only of lowercase English letters.

My Solutions:

class Solution {
    public boolean isSubsequence(String s, String t) {
        if (s.length() == 0) return true;
        if (s.length() > t.length()) return false;
        int index = 0;
        for (int i = 0; i < t.length(); i++) {
            if (s.charAt(index) == t.charAt(i)) {
                index++;
                if (index == s.length()) return true;
            } 
        }
        return index == s.length();
    }
}

Follow up: Suppose there are lots of incoming s, say s1, s2, ..., sk where k >= 109, and you want to check one by one to see if t has its subsequence. In this scenario, how would you change your code?

792. Number of Matching Subsequences

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.

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

• 1 <= words.length <= 5000

• 1 <= words[i].length <= 50

• s and words[i] consist of only lowercase English letters.

My Solutions:

class Solution {
    // 方法 1：同392，把words里的每个word循环一遍。优化：只循环没有见过的word
    // public int numMatchingSubseq(String s, String[] words) {
    //     if (s.length() == 0) return words.length;
    //     int count = 0;
    //     HashMap<String, Integer> freq = new HashMap<>();
    //     for (String word : words) freq.put(word, freq.getOrDefault(word, 0) + 1);
    //     // Time Limit Exceeded without caching
    //     // for (int i = 0; i < words.length; i++) {
    //     //     if (isSubseq(s, words[i])) count++;
    //     // }
    //     for (String word: freq.keySet()) {
    //         if (isSubseq(s, word)) count += freq.get(word);
    //     }
    //     return count;
    // }

    // private boolean isSubseq(String t, String s) {
    //     int index = 0;
    //     for (int i = 0; i < t.length(); i++) {
    //         if (s.charAt(index) == t.charAt(i)) {
    //             index++;
    //             if (index == s.length()) return true;
    //         } 
    //     }
    //     return index == s.length();
    // }

    // 方法2：
    // Use a map and put the characters of s as the key and the corresponding strings which start with that char in words as the value.
    // Iterate over s and after removing the queue from the value we remove one char and check if the len is equal to 0. If yes we increment count
    // If no we add it back to the map to its corresponding char if it exists.
    public int numMatchingSubseq(String s, String[] words) {
        if (s.length() == 0) return words.length;
        int count = 0;
        HashMap<Character, Queue<String>> map = new HashMap<>();
        for (int i = 0; i < 26; i++) {
            map.put((char)('a' + i), new LinkedList<>());
        }

        for (String word : words) {
            char c = word.charAt(0);
            if (map.containsKey(c)) map.get(c).offer(word);
        }

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!map.containsKey(c)) continue;

            Queue<String> q = map.get(c);
            int size = q.size();
            for (int j = 0; j < size; j++) {
                String str = q.poll();
                if (str.length() == 1) count++;
                else {
                    char nextChar = str.charAt(1);
                    if (map.containsKey(nextChar)) {
                         map.get(nextChar).offer(str.substring(1));
                    }
                }
            }
        }
        return count;
    }
}