Is Subsequence

这题本身是O(n)的时间复杂度，n是t的length，m是s的length。用双指针。

public class Solution {
    public boolean isSubsequence(String s, String t) {
        if (s.length() == 0) {
            return true;
        } else if (s.length() > t.length()) {
            return false;
        }

        int j = 0;
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i), d = s.charAt(j);
            if (c == d) {
                j++;
                if (j == s.length()) {
                    return true;
                }
            }
        }
        return false;
    }
}

解法二：遍历word，对于每一个character，在t里调用indexOf(character, fromIndex)。时间复杂度为O(m * logN)，这是不小的优化，把基本很长的数组的length的问题，转化为基于word length的问题。

public class Solution {
    public boolean isSubsequence(String s, String t) {
        if (s.length() == 0) {
            return true;
        } else if (s.length() > t.length()) {
            return false;
        }

        int prev = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            int pos = t.indexOf(c, prev);
            if (pos == -1) return false;
            prev = pos + 1;
        }
        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?

Follow up里，如果用双指针的做法，一个有k个word要查，n是t的length，那时间复杂度就是O(kn)。

这里可以先存下每一个character出现的位置，然后binary search。时间复杂度变成了O(k * m * logN)，优化了不少，因为t的length可以非常的长，而每一个word的平均长度m其实就不多。

public class Solution {
    public boolean isSubsequence(String s, String t) {
        if (s.length() == 0) {
            return true;
        } else if (s.length() > t.length()) {
            return false;
        }

        Map<Character, List<Integer>> map = new HashMap<Character, List<Integer>>();
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            if (!map.containsKey(c)) {
                map.put(c, new ArrayList<Integer>());
            }
            map.get(c).add(i);
        }

        int prev = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!map.containsKey(c)) {
                return false;
            }

            List<Integer> list = map.get(c);
            int pos = binarySearch(prev, list, 0, list.size() - 1); // find the first index greater than or equal to prev
            if (pos == -1) {
                return false;
            }
            prev = pos + 1;
        }
        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) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return list.get(start) >= index ? list.get(start) : -1;
    }
}