792.Number-of-Matching-Subsequences

792. 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);
}
}