792. Number of Matching Subsequences

https://leetcode.com/problems/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.

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 * 104 	
1 <= words.length <= 5000 	
1 <= words[i].length <= 50 	
s and words[i] consist of only lowercase English letters.

  • code
class Solution {
    public int numMatchingSubseq(String S, String[] words) {
        int ans = 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));

        for (char c: S.toCharArray()) {
            ArrayList<Node> old_bucket = heads[c - 'a'];
            heads[c - 'a'] = new ArrayList<Node>();

            for (Node node: old_bucket) {
                node.index++;
                if (node.index == node.word.length()) {
                    ans++;
                } else {
                    heads[node.word.charAt(node.index) - 'a'].add(node);
                }
            }
            old_bucket.clear();
        }
        return ans;
    }

}

class Node {
    String word;
    int index;
    public Node(String w, int i) {
        word = w;
        index = i;
    }
}
  • code TLE
class Solution {
    public int numMatchingSubseq(String s, String[] words) {
        int count = 0;
        for (String word: words){
            int i = 0;
            int wi = 0;
            while (i <= s.length()){
                if (wi == word.length()){
                    count++;
                    break;
                }
                if (i == s.length()) break;
                if (s.charAt(i) == word.charAt(wi)){
                    i++;
                    wi++;
                }else{
                    i++;
                }
            }
        }
        return count;
    }
}