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.

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

Solution

Tracing the s, and to know if any of the words have been satisfied during the tracing.

The problem is how to keep tracing all the words?

We use an array with size 2 to keep the current tracing status of a word. [i, j]

where i is the index of the words, tell us what is the word we are examining., and j is the chatIndex of the word, tell us what is the index we are checking in the wordi.

We also put those records into a Map, which its key denotes the char that we are looking.

public int findSubStringCount(String s, String[] words){
    List<int[]>[] records = new List[128];
    for(int i = 0; i < 128; i++){
        records[i] = new ArrayList<int[]>();
    }
    for(int i = 0; i < words.length; i++){
        char c = words[i].charAt(0);
        records[c-'a'].add(new int[]{i, 0});
    }
    int count = 0;
    for(int i = 0; i < s.length(); i++){
        char c = s.charAt(i);
        
        List<int[]> waitingList = new ArrayList<>(records[c-'a']);
        records[c-'a'].clear();
        
        for(int[] pair : waitingList){
            int wordIndex = pair[0];
            int index = pair[1];
            String word = words[wordIndex];
            if(index == word.length()-1){
                count++;
                continue;
            }else{
                char newc = word.charAt(index+1);
                records[newc-'a'].add(new int[]{wordIndex, index+1});
            }
        }
    }
    return count;
}