792. Number of Matching Subsequences

开源项目
1

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

思路

以下面内容举例：

S = "abcde"
words = ["a", "bb", "acd", "ace"]

首先，将words根据第一个字符进行分类：

'a':  ["(a)", "(a)cd", "(a)ce"]
'b':  ["(b)b"]

然后遍历S，S的第一个字符是’a’，发现words中，有一个刚好匹配"a"，于是放入None：

'b':  ["(b)b"]
'c':  ["a(c)d", "a(c)e"]
None: ["a"]

S的下一个字符是’b’，于是words中有一部分匹配，如果匹配，就继续匹配下一个字符：

'b':  ["b(b)"]
'c':  ["a(c)d", "a(c)e"]
None: ["a"]

然后是 ‘c’ :

'b':  ["b(b)"]
'd':  ["ac(d)"]
'e':  ["ac(e)"]
None: ["a"]

然后是 ‘d’ :

'b':  ["b(b)"]
'e':  ["ac(e)"]
None: ["a", "acd"]

然后是 ‘e’ :

'b':  ["b(b)"]
None: ["a", "acd", "ace"]

最后返回有多个wrod被完全匹配：3

java

```java
class Solution {
    public int numMatchingSubseq(String S, String[] words) {
        
        Map<Character, Deque<String>> map = new HashMap<>();
        for (char c = 'a'; c <= 'z'; c++) {
            map.putIfAbsent(c, new LinkedList<String>());
        }
        for (String word : words) {
            map.get(word.charAt(0)).addLast(word);
        }

        int count = 0;
        for (char c : S.toCharArray()) {
            Deque<String> queue = map.get(c);
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String word = queue.removeFirst();
                if (word.length() == 1) {
                    count++;
                } else {
                    map.get(word.charAt(1)).addLast(word.substring(1));
                }
            }
        }
        return count;
    }
}

python

class Solution:
    def numMatchingSubseq(self, S: str, words: List[str]) -> int:
        rec=collections.defaultdict(list)
        res = 0
        for word in words:
            rec[word[0]].append(word)
        for s in S:
            for i in range(len(rec[s])):
                word = rec[s].pop(0)
                if len(word) == 1:
                    res += 1
                else :
                    rec[word[1]].append(word[1:])
                
        return res
2 
public class chazhao {
    public int numMatchingSubseq(String S, String[] words) {
        //统计不匹配的次数
        int stsize=0;
        for(String zi:words) {
            int temp = 0;
            for (int i = 0; i < zi.length(); i++) {
                //获取到子集的char,查找S里是否存在，存在返回下标，否则为-1
                //indexOf(char,int)char:查找样本，int：查找的下标位置
                int indexOf = S.indexOf(zi.charAt(i), temp);
                System.out.println(zi.charAt(i));
                if(indexOf == -1)
                {
                    System.out.println("-1跳出");
                    stsize++;
                    break;
                }
                //记录下次查找S的下标位置
                temp = indexOf + 1;
            }

        }
        int  num = words.length - stsize;
        return num;
    }