Version #2 List of words waiting for the next character
把所有的words分类成他们下一个需要match的character，如果在s里面遇到了这个character就把这些word取出来重新分类
这里space可以继续优化，就是不存每个word的string而是存word的index
Time O(L*N) - L is the length of string, N is the number of words?
Space O(MN) - total length of all words
Runtime: 119 ms, faster than 76.38% of Java online submissions for Number of Matching Subsequences.
Memory Usage: 118.8 MB, less than 10.36% of Java online submissions for Number of Matching Subsequences.
class Solution {
public int numMatchingSubseq(String s, String[] words) {
// use an array for words that are waiting for the next character
List<Pair<String, Integer>>[] candidates = new ArrayList[26];
for (int i = 0; i < 26; i++) {
candidates[i] = new ArrayList<>();
}
for (String word : words) {
candidates[word.charAt(0) - 'a'].add(new Pair<>(word, 0));
}
int result = 0;
for (int i = 0; i < s.length(); i++) {
List<Pair<String, Integer>> candidate = candidates[s.charAt(i) - 'a'];
candidates[s.charAt(i) - 'a'] = new ArrayList<>();
for (Pair<String, Integer> p : candidate) {
String word = p.getKey();
int nextPointer = p.getValue() + 1;
if (nextPointer == word.length()) {
result++;
continue;
}
candidates[word.charAt(nextPointer) - 'a'].add(new Pair<>(word, nextPointer));
}
}
return result;
}
}
Version #1 2D array for next occurrence
Time O(L + MN) - L is the string length, MN is the total length of all words
Space O(26L) ~ O(L)
Runtime: 215 ms, faster than 33.45% of Java online submissions for Number of Matching Subsequences.
Memory Usage: 119.5 MB, less than 7.67% of Java online submissions for Number of Matching Subsequences.
class Solution {
public int numMatchingSubseq(String s, String[] words) {
int[][] nextIndices = new int[s.length()][];
int[] nextIndex = new int[26];
Arrays.fill(nextIndex, -1);
for (int i = s.length() - 1; i >= 0; i--) {
nextIndices[i] = nextIndex.clone();
nextIndex[s.charAt(i) - 'a'] = i;
}
int result = 0;
for (String word: words) {
int n = 0;
int i = 0;
for (i = 0; i < word.length(); i++) {
if (i == 0) {
n = nextIndex[word.charAt(i) - 'a'];
} else {
n = nextIndices[n][word.charAt(i) - 'a'];
}
if (n == -1) {
break;
}
}
if (i == word.length()) {
result++;
}
}
return result;
}
}
一刷
Version #1 Mem 2D array of next occurrence
39.72 %
class Solution {
public int numMatchingSubseq(String S, String[] words) {
char[] chars = S.toCharArray();
int[][] mem = new int[chars.length][26];
int length = chars.length;
Arrays.fill(mem[length - 1], -1);
for (int k = chars.length - 2; k >= 0; k--) {
char c = chars[k + 1];
for (int i = 0; i < 26; i++) {
if (i == c - 'a') {
mem[k][i] = k + 1;
} else {
mem[k][i] = mem[k + 1][i];
}
}
}
int count = 0;
for (String word : words) {
int pointer = 0;
if (word.charAt(0) == chars[0]) {
pointer = -1;
} else {
pointer = mem[0][word.charAt(0) - 'a'];
}
int i = 0;
for (i = 1; i < word.length(); i++) {
char curr = word.charAt(i);
int next = 0;
if (pointer == -1) {
next = mem[0][curr - 'a'];
} else {
next = mem[pointer][curr - 'a'];
}
if (next == -1) {
break;
}
pointer = next;
}
if (i == word.length()) {
count++;
}
}
return count;
}
}
39.72 %
class Solution {
public int numMatchingSubseq(String S, String[] words) {
char[] chars = S.toCharArray();
int[][] mem = new int[chars.length][26];
int length = chars.length;
Arrays.fill(mem[length - 1], -1);
for (int k = chars.length - 2; k >= 0; k--) {
char c = chars[k + 1];
for (int i = 0; i < 26; i++) {
if (i == c - 'a') {
mem[k][i] = k + 1;
} else {
mem[k][i] = mem[k + 1][i];
}
}
}
int count = 0;
for (String word : words) {
int pointer = 0;
if (word.charAt(0) == chars[0]) {
pointer = -1;
} else {
pointer = mem[0][word.charAt(0) - 'a'];
}
int i = 0;
for (i = 1; i < word.length(); i++) {
char curr = word.charAt(i);
int next = 0;
if (pointer == -1) {
next = mem[0][curr - 'a'];
} else {
next = mem[pointer][curr - 'a'];
}
if (next == -1) {
break;
}
pointer = next;
}
if (i == word.length()) {
count++;
}
}
return count;
}
}
No comments:
Post a Comment