leetcode 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

判断words里面有几个是s的子串。
子串指字母都在s里，且保持相对顺序，在s中不一定是连续的。

思路：

1.binary search
可以直接用Brute force，每个word都遍历一遍s，判断是不是子串，
但这种方法在大量重复word的时候会TLE，可用一个hashmap保存下每个word判断的结果。

但是每次遍历s用的都是线性时间复杂度，用binary search的话可以把这种判断子串的时间缩短到O(logn)

具体怎么做，首先把s中的字母出现的位置都保存在list里，因为字母只有26个，所以用下标i对应第 i 个字母，
字母对应的位置保存list, 即各字母都在什么位置出现。

然后遍历word的时候，只需要顺次找到字母出现的位置，
找到前一个字母出现的位置之后，记下下标left, 下一次在left+1往后的位置找下一个字母，找不到就返回false.

同时，用2个hashset记录下已经判断过是子串和不是子串的word.

class Solution {
    List<List<Integer>> pos;
    HashSet<String> set = new HashSet<>();
    HashSet<String> not = new HashSet<>();
    
    public int numMatchingSubseq(String s, String[] words) {
        int res = 0;
        pos = new ArrayList<>();
        for(int i = 0; i < 26; i ++) {
            pos.add(new ArrayList<Integer>());
        }
        
        //保存每个字母出现的位置
        for(int i = 0; i < s.length(); i++) {
            pos.get(s.charAt(i) - 'a').add(i);
        }
        
        for(String word : words) {
            if(isMatch(word)) {
                set.add(word);
                res ++;
            } else {
                not.add(word);
            }     
        }
        return res;
    }
    
    boolean isMatch(String word) {
        if(set.contains(word)) return true;
        if(not.contains(word)) return false;
        int left = -1;
        
        for(char ch : word.toCharArray()) {
            List<Integer> curPos = pos.get(ch - 'a');
            //找left+1,即下一index,可能会找不到，但是我们要的不是确切的left+1,而是比它大的即可，
            //所以要找到需要插入的位置，即返回的负的index
            int index = Collections.binarySearch(curPos, left+1);
            if(index < 0) index = -index -1;
            if(index >= curPos.size()) return false;
            left = curPos.get(index);
        }
        return true;
    }
}
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

2.queue

上面方法一是对每个单词，都要遍历一次s来进行匹配，
那么有没有只遍历一次s，同时达到匹配所有单词的效果？

如果想达到这种效果，第一直觉应该是每遍历到s的一个字母，我们都要去匹配每个单词，
单词中如果有字母和s的这个字母匹配，就把单词的遍历下标+1，
那么每个单词都应该有一个遍历的下标，这么多下标要怎么维护呢？

定义一个Item, 里面是单词和目前遍历到的下标。

首先把words做一个处理，把words中每个单词首字母对应的位置加入一个queue,
这个queue保存的是现在每个单词和它们的遍历下标：0，

后面queue保存的是和当前s遍历到的字母 匹配的所有item（单词和它们相应的字母下标）。

然后遍历s中的字母，每个字母取出对应的queue, queue里面有所有以这个字母开头的单词，
字母匹配之后，把对应单词的当前下标+1，也就是下一次将匹配的字母下标，
如果下标和单词长度一致，认为已经遍历完，该单词是子串，结果+1.

class Solution {
    class Item {
        String word;
        int index;
        public Item (String s, int i) {
            word = s;
            index = i;
        }
    }
    public int numMatchingSubseq(String S, String[] words) {
        Queue<Item>[] dict = new Queue[26];
        for (int i = 0; i < dict.length; i++) {
            dict[i] = new LinkedList<>();
        }

        for (String word :words) {
            if (word.length() > 0) {
                dict[word.charAt(0) - 'a'].add(new Item(word, 0));
            }
        }

        int count = 0;
        for (char c : S.toCharArray()) {
            Queue<Item> queue = dict[c - 'a'];
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Item top = queue.remove();
                top.index++;
                if (top.index == top.word.length()) {
                    count++;
                } else {
                    dict[top.word.charAt(top.index) - 'a'].add(top);
                }
            }
        }

        return count;
    }
}
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39