二刷 08/2022
Version #1 Two Pointers
写了一个bug就是当while循环过了之后只是表示有可能有match的character，ti需要继续加1，否则会发生同样的character重复match
Time O(T) - length of the target string
Space O(1)
Runtime: 4 ms, faster than 11.01% of Java online submissions for Is Subsequence.
Memory Usage: 41.9 MB, less than 66.53% of Java online submissions for Is Subsequence.
class Solution {
public boolean isSubsequence(String s, String t) {
int ti = 0;
int si = 0;
for (si = 0; si < s.length(); si++) {
while (ti < t.length() && s.charAt(si) != t.charAt(ti)) {
ti++;
}
if (ti == t.length()) {
break;
}
ti++;
}
return si == s.length();
}
}
Version #2 Binary Search for follow up
Time O(T) + O(SlogT) for each input S
Space O(T)
Runtime: 9 ms, faster than 5.74% of Java online submissions for Is Subsequence.
Memory Usage: 43.5 MB, less than 5.13% of Java online submissions for Is Subsequence.
class Solution {
public boolean isSubsequence(String s, String t) {
Map<Character, List<Integer>> indices = new HashMap<>();
for (int i = 0; i < t.length(); i++) {
char tc = t.charAt(i);
indices.putIfAbsent(tc, new ArrayList<>());
indices.get(tc).add(i);
}
int ti = 0;
for (int i = 0; i < s.length(); i++) {
int ni = search(indices.getOrDefault(s.charAt(i), new ArrayList<>()), ti);
if (ni == -1) {
return false;
}
ti = ni + 1;
}
return true;
}
// find the first index larger than or equals to target
private int search(List<Integer> indices, int target) {
if (indices.size() == 0) {
return -1;
}
int start = 0;
int end = indices.size() - 1;
while (start < end) {
int mid = start + (end - start) / 2;
if (indices.get(mid) >= target) {
end = mid;
} else {
start = mid + 1;
}
}
if (indices.get(start) >= target) {
return indices.get(start);
}
return -1;
}
}
28.20 %
class Solution {
public boolean isSubsequence(String s, String t) {
if (s == null || t == null || t.length() < s.length()) {
return false;
}
int ps = 0;
int pt = 0;
for (ps = 0; ps < s.length(); ps++) {
while (pt < t.length() && t.charAt(pt) != s.charAt(ps)) {
pt++;
}
if (pt == t.length()) {
return false;
} else {
pt++;
}
}
return true;
}
}
Version #2 Follow Up -> Binary Search
二刷
9.45 %
class Solution {
public boolean isSubsequence(String s, String t) {
if (s == null || t == null || s.length() > t.length()) {
return false;
}
Map<Character, List<Integer>> map = init(t);
return check(s, map);
}
// key->char, value->indices of this char
private Map<Character, List<Integer>> init(String t) {
Map<Character, List<Integer>> map = new HashMap<>();
for (int i = 0; i < t.length(); i++) {
char c = t.charAt(i);
if (!map.containsKey(c)) {
map.put(c, new ArrayList<>());
}
map.get(c).add(i);
}
return map;
}
private boolean check(String s, Map<Character, List<Integer>> map) {
int curr = 0;
int length = s.length();
List<Integer> indices = null;
for (int i = 0; i < length; i++) {
indices = map.get(s.charAt(i));
if (indices == null) {
return false;
}
// find the 1st index larger than or equal to curr
int start = 0;
int end = indices.size() - 1;
while (start < end) {
int mid = start + (end - start) / 2;
if (indices.get(mid) < curr) {
start = mid + 1;
} else {
end = mid;
}
}
if (indices.get(start) < curr) {
return false;
}
curr = indices.get(start) + 1;
}
return true;
}
}
一刷
14.79 %
Binary Search 还是写的不好
对于找第一个大于pt的index，如果最后停在start == end时候，这个值是有可能小于pt的，所以最后还是需要额外check一下
class Solution {
public boolean isSubsequence(String s, String t) {
if (s == null || t == null) return false;
// public static ArrayList<myObject>[] a = (ArrayList<myObject>[])new ArrayList<?>[2];
List<Integer>[] map = (ArrayList<Integer>[])new ArrayList<?>[26];
for (int i = 0; i < t.length(); i++) {
int index = t.charAt(i) - 'a';
if (map[index] == null) map[index] = new ArrayList<>();
map[index].add(i);
}
// ps pt
// s = " a b c", t = " a h b g d c"
int pt = 0;
for (int ps = 0; ps < s.length(); ps++) {
if (pt >= t.length()) return false;
// t doesn't have this character at all
if (map[s.charAt(ps) - 'a'] == null) return false;
// Find the 1st index >= ps, if not found, return -1
int next = binarySearch(pt, map[s.charAt(ps) - 'a']);
//System.out.println(s.charAt(ps) + " " + next + "pt: " + pt);
if (next == -1) return false;
pt = next + 1;
}
return true;
}
private int binarySearch(int pt, List<Integer> list) {
int start = 0;
int end = list.size() - 1;
// There's no duplicate in list
while (start < end) {
int mid = start + (end - start) / 2;
if (list.get(mid) == pt) return pt;
if (list.get(mid) < pt) {
start = mid + 1;
} else {
end = mid;
}
}
if (list.get(start) < pt) return -1;
else return list.get(start) ; // Very important
}
}
No comments:
Post a Comment