/
NumberOfSubsequence.java
55 lines (46 loc) · 1.61 KB
/
NumberOfSubsequence.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// https://leetcode.com/problems/number-of-matching-subsequences/
class Solution {
public int numMatchingSubseq(String s, String[] words) {
Subsequencer sb = new Subsequencer(s);
int count = 0;
for (String word: words) {
if (sb.isSubsequence(word)) {
count++;
}
}
return count;
}
class Subsequencer {
private int[][] indexMap;
private int[] indexTrack;
Subsequencer(String s) {
indexMap = new int[26][s.length()];
indexTrack = new int[26];
for (int[] row: indexMap) {
Arrays.fill(row, Integer.MAX_VALUE);
}
for (int i = 0; i < s.length(); i++) {
int index = s.charAt(i) - 'a';
indexMap[index][indexTrack[index]++] = i;
}
}
boolean isSubsequence(String w) {
int track = -1;
for (int x: w.getBytes()) {
int index = x - 'a';
int searched = Arrays.binarySearch(indexMap[index], track);
if (searched < 0) {
searched = -searched - 1;
} else {
searched = searched + 1;
}
if (searched >= indexMap[index].length || indexMap[index][searched] == Integer.MAX_VALUE) {
return false;
} else {
track = indexMap[index][searched];
}
}
return true;
}
}
}