792.Number-of-Matching-Subsequences.md

792. Number of Matching Subsequences

---

题目地址

https://leetcode.com/problems/number-of-matching-subsequences/

题目描述

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

代码

Approach #1 Next Letter Pointers

Time: O(S.length+∑words[i].length) && Space: O(S.length)

class Solution {
  public int numMatchingSubseq(String S, String[] words) {
		int ans = 0;
    ArrayList<Node>[] heads = new ArrayList[26];
    for (int i = 0; i < 26; i++) {
      heads[i] = new ArrayList<Node>();
    }
    
    for (String word: words) {
      heads[word.charAt(0) - 'a'].add(new Node(word, 0));
    }
    
    for (char c: S.toCharArray()) {
      ArrayList<Node> old_bucket = heads[c - 'a'];
      heads[c - 'a'] = new ArrayList<Node>();
      
      for (Node node: old_bucket) {
        node.index++;
        if (node.index == node.word.length()) {
          ans++;
        } else {
          heads[node.word.charAt(node.index) - 'a'].add(node); 
        }
      }
      old_bucket.clear();
    }
    return ans;
  }
}

class Node {
  String word;
  int index;
  public Node(String w, int i) {
    word = w;
    index = i;
  }
}

Approach #2 Brute Force [Time Limit Exceeded]

class Solution {
  char[] ca, cb;
  public int numMathingSubseq(String S, String[] words) {
    int ans = 0;
    ca = S.toCharArray();
    for (String word: words) {
      if (subseq(word))		ans++;
    }
    return ans;
  }
  
  public boolean subseq(String word) {
    int i = 0;
    cb = word.toCharArray();
    for (char c: ca) {
      if (i < cb.length && c == cb[i])		i++;
    }
    return (i == cb.length);
  }
}