【1117】

792. 匹配子序列的单词数     中等       相关企业

给定字符串 s 和字符串数组 words, 返回  words[i] 中是s的子序列的单词个数 。

字符串的 子序列 是从原始字符串中生成的新字符串，可以从中删去一些字符(可以是none)，而不改变其余字符的相对顺序。

• 例如， “ace” 是 “abcde” 的子序列。

示例 1:

输入: s = "abcde", words = ["a","bb","acd","ace"]
输出: 3
解释: 有三个是 s 的子序列的单词: "a", "acd", "ace"。

Example 2:

输入: s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]
输出: 2

提示:

• 1 <= s.length <= 5 * 104
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 50
• words[i]和 s 都只由小写字母组成。

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

 1 class Solution {
 2     public int numMatchingSubseq(String s, String[] words) {
 3         List<Integer>[] pos = new List[26];
 4         for (int i = 0; i < 26; ++i) {
 5             pos[i] = new ArrayList<Integer>();
 6         }
 7         for (int i = 0; i < s.length(); ++i) {
 8             pos[s.charAt(i) - 'a'].add(i);
 9         }
10         int res = words.length;
11         for (String w : words) {
12             if (w.length() > s.length()) {
13                 --res;
14                 continue;
15             }
16             int p = -1;
17             for (int i = 0; i < w.length(); ++i) {
18                 char c = w.charAt(i);
19                 if (pos[c - 'a'].isEmpty() || pos[c - 'a'].get(pos[c - 'a'].size() - 1) <= p) {
20                     --res;
21                     break;
22                 }
23                 p = binarySearch(pos[c - 'a'], p);
24             }
25         }
26         return res;
27     }
28 
29     public int binarySearch(List<Integer> list, int target) {
30         int left = 0, right = list.size() - 1;
31         while (left < right) {
32             int mid = left + (right - left) / 2;
33             if (list.get(mid) > target) {
34                 right = mid;
35             } else {
36                 left = mid + 1;
37             }
38         }
39         return list.get(left);
40     }
41 
42 
43 }