forked from pxu/Algorithm
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathNumberOfMatchingSubseqs.java
More file actions
34 lines (30 loc) · 932 Bytes
/
NumberOfMatchingSubseqs.java
File metadata and controls
34 lines (30 loc) · 932 Bytes
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
import java.util.*;
public class NumberOfMatchingSubseqs {
private boolean isSubseq(String w, String S) {
if(w.length() == 0) return true;
int i = 0, j = 0;
for(; i<S.length(); ++i) {
if(S.charAt(i) == w.charAt(j)) j += 1;
if(j == w.length()) break;
}
return j == w.length();
}
public int numMatchingSubseq(String S, String[] words) {
int results = 0;
Set<String> subseq = new HashSet<> ();
Set<String> notSubseq = new HashSet<> ();
for(String w: words) {
if(subseq.contains(w)) results += 1;
else if(notSubseq.contains(w)) continue;
else {
if(isSubseq(w, S)) {
results += 1;
subseq.add(w);
} else {
notSubseq.add(w);
}
}
}
return results;
}
}