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

题解：

For each word in words, its first char of each word is the waiting char.

When iterate s, the currrent char c release corresponding waiting group in words, remove it and see the next waiting char.

If there is none, then we find a subsequence, res++.

To make sure it is liner, we use LinkedList<Character> to represent String.

Time Complexity: O(m*n + len). m = words.length. n is word length. len = s.length().

Space: O(m*n + len).

AC Java:

 1 class Solution {
 2     public int numMatchingSubseq(String s, String[] words) {
 3         int res = 0;
 4         List<LinkedList<Character>> [] waiting = new List[26];
 5         for(int i = 0; i < 26; i++){
 6             waiting[i] = new ArrayList<LinkedList<Character>>();
 7         }
 8         
 9         for(String w : words){
10             LinkedList<Character> que = new LinkedList<>();
11             for(char letter : w.toCharArray()){
12                 que.add(letter);
13             }
14             
15             waiting[w.charAt(0) - 'a'].add(que);
16         }
17         
18         for(char c : s.toCharArray()){
19             List<LinkedList<Character>> cur = waiting[c - 'a'];
20             waiting[c - 'a'] = new ArrayList<LinkedList<Character>>();
21             for(LinkedList<Character> item : cur){
22                 item.pollFirst();
23                 if(item.size() == 0){
24                     res++;
25                 }else{
26                     waiting[item.peekFirst() - 'a'].add(item);
27                 }
28             }
29         }
30         
31         return res;
32     }
33 }