這題本身就是O(n)一趟，很簡(jiǎn)單就不貼出來了；貼一下follow up的解法，思路就是把T的每個(gè)字母當(dāng)作key，字母所在的index加入list作為value，然后就利用二分搜索來找s中某個(gè)字母的下一個(gè)位置。

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);

}