LeetCode [792] Number of Matching Subsequences

 792. Number of Matching Subsequences

Medium

Given string S and a dictionary of words words, find the number of words[i] that is a subsequence of S.

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

Note:

• All words in words and S will only consists of lowercase letters.
• The length of S will be in the range of [1, 50000].
• The length of words will be in the range of [1, 5000].
• The length of words[i] will be in the range of [1, 50].

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

class Solution { public int numMatchingSubseq(String S, String[] words) { List<StringBuilder>[] list = new List[128]; for(char c = 'a'; c<='z'; c++) list[c] = new ArrayList<>(); for(String w : words){ list[w.charAt(0)].add(new StringBuilder(w)); } int ret = 0; for(char c : S.toCharArray()){ List<StringBuilder> temp = list[c]; list[c] = new ArrayList<>(); for(StringBuilder it : temp) { it.deleteCharAt(0); if(it.length()!=0){ list[it.charAt(0)].add(it); }else ret++; } } return ret; } }