0792. Number of Matching Subsequences - kumaeki/LeetCode GitHub Wiki

0792. 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 * 10^4
  • 1 <= words.length <= 5000
  • 1 <= words[i].length <= 50
  • s and words[i] consist of only lowercase English letters.

解法1

首先想到的是把所有的words放进字典里, 然后用 s 遍历字典, 找到所有匹配的字符并计数. 但是超时了.

class Solution {
    public int numMatchingSubseq(String s, String[] words) {
        Node root = prepareNode(words);
        return getCount(root, s, 0);
    }
    
    private Node prepareNode(String[] words){
        Node root = new Node('#');
        for(String w : words){
            Node node = root;
            for(char c : w.toCharArray()){
                if(node.next[c - 'a'] == null)
                    node.next[c - 'a'] = new Node(c);

                node = node.next[c - 'a'];
            }
            node.isEnd++;
        }
        return root;
    }
    
    private int getCount(Node node, String s, int index){
        if(index == s.length())
            return 0;
        
        int res = 0;
        
        Node next = node.next[s.charAt(index) - 'a'];
        if(next != null){
             if(next.isEnd > 0){
                 res += next.isEnd;
                 next.isEnd = 0;
             }
            res += getCount(next, s, index + 1);
        }
        
        return res + getCount(node, s, index + 1);
    }
    
    private class Node{
        Node[] next;
        int isEnd;
        
        public Node(char v){
            next = new Node[26];
            isEnd = 0;
        }
    }
}

#解法2

class Solution {
    public int numMatchingSubseq(String S, String[] words) {
        // 用map来存储以a到z为首字符的字符串的列表
        Map<Character, LinkedList<String>> map = new HashMap<Character, LinkedList<String>>();
        for (char c = 'a'; c <= 'z'; c++)
            map.putIfAbsent(c, new LinkedList<String>());

        // 将所有的words放入map
        for (String w : words)
            map.get(w.charAt(0)).addLast(w);

        int res = 0;
        // 对于s中的每一个字符
        for (char c : S.toCharArray()) {
            // 找到所有以当前字符c开头的字符串
            LinkedList<String> list = map.get(c);
            for (int i = 0, len = list.size(); i < len; i++) {
                String str = list.removeFirst();
                // 如果字符串长度为1, 那么肯定是符合条件的, 结果数 + 1
                if (str.length() == 1)
                    res++;
                // 如果不为1, 那么去掉头字符, 将剩下的字符串存入map中
                // 这个步骤每次都会将符合条件的字符长度减1, 直到将长度减少为1
                else
                    map.get(str.charAt(1)).addLast(str.substring(1));
            }
        }
        return res;
    }
}

#解法3 解法2中对每个word反复取子字符串其实也很花费时间.

class Solution {
      public int numMatchingSubseq(String S, String[] words) {
        Map<Character, LinkedList<Item>> map = new HashMap<Character, LinkedList<Item>>(30);
        for (char c = 'a'; c <= 'z'; c++)
            map.putIfAbsent(c, new LinkedList<Item>());

        for (String w : words)
            map.get(w.charAt(0)).addLast(new Item(w, 0));

        int res = 0;
        for (char c : S.toCharArray()) {
            LinkedList<Item> list = map.get(c);
            for (int i = 0, len = list.size(); i < len; i++) {
                Item item = list.removeFirst();
                if (item.index == item.word.length() - 1)
                    res++;
                else{
                    item.index++;
                    map.get(item.word.charAt(item.index)).addLast(item);
                }
            }
        }
        return res;
    }
    
    // 用Item来保存原始字符和计算下标, 避免频繁的substring
    class Item{
        String word;
        int index;
        
        public Item(String word, int index){
            this.word = word;
            this.index = index;
        }
    }
}
⚠️ **GitHub.com Fallback** ⚠️