这题本身就是O(n)一趟，很简单就不贴出来了；贴一下follow up的解法，思路就是把T的每个字母当作key，字母所在的index加入list作为value，然后就利用二分搜索来找s中某个字母的下一个位置。
from:
public boolean isSubsequence(String s, String t) {
if (s == null || t == null) return false;
Map<Character, List<Integer>> map = new HashMap<>(); //<character, index>
//preprocess t
for (int i = 0; i < t.length(); i++) {
char curr = t.charAt(i);
if (!map.containsKey(curr)) {
map.put(curr, new ArrayList<Integer>());
}
map.get(curr).add(i);
}
int prev = -1; //index of previous character
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (map.get(c) == null) {
return false;
} else {
List<Integer> list = map.get(c);
prev = binarySearch(prev, list, 0, list.size() - 1);
if (prev == -1) {
return false;
}
prev++;
}
}
return true;
}
private int binarySearch(int index, List<Integer> list, int start, int end) {
while (start <= end) {
int mid = start + (end - start) / 2;
if (list.get(mid) < index) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return start == list.size() ? -1 : list.get(start);
}
