392. Is Subsequence - cocoder39/coco39_LC GitHub Wiki
public boolean isSubsequence(String s, String t) {
int start = 0;
for (int i = 0; i < s.length(); i++) {
while (start < t.length() && s.charAt(i) != t.charAt(start)) {
start++;
}
if (start == t.length() || s.charAt(i) != t.charAt(start)) {
return false;
}
start++;
}
return true;
}
Follow up: If there are lots of incoming S, say S1, S2, ... , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?
Which is basically 792. Number of Matching Subsequences
public boolean isSubsequence(String s, String t) {
List<Integer>[] charByIdx = new List[256];
for (int i = 0; i < t.length(); i++) {
List<Integer> idxes = charByIdx[t.charAt(i)];
if (idxes == null) {
idxes = new ArrayList<>();
}
idxes.add(i);
charByIdx[t.charAt(i)] = idxes;
}
int start = 0;
for (int i = 0; i < s.length(); i++) {
List<Integer> idxes = charByIdx[s.charAt(i)];
start = helper(idxes, start);
if (start == -1) {
return false;
}
start++;
}
return true;
}
private int helper(List<Integer> idxes, int start) {
if (idxes == null || idxes.isEmpty()) {
return -1;
}
int left = 0;
int right = idxes.size() - 1;
while (right - left > 1) {
int mid = left + (right - left) / 2;
if (idxes.get(mid) < start) {
left = mid;
} else {
right = mid;
}
}
if (idxes.get(left) >= start) {
return idxes.get(left);
}
if (idxes.get(right) >= start) {
return idxes.get(right);
}
return -1;
}