Leetcode - Is Subsequence

My code:

public class Solution {
    public boolean isSubsequence(String s, String t) {
        if (s == null || t == null) {
            return false;
        }
        else if (t.length() < s.length()) {
            return false;
        }
        
        int pre = 0;
        for (int i = 0; i < s.length(); i++) {
            char curr = s.charAt(i);
            int index = t.indexOf("" + curr, pre);
            if (index == -1) {
                return false;
            }
            pre = index + 1;
        }
        return true;
    }
}

reference:
https://discuss.leetcode.com/topic/57205/java-only-2ms-much-faster-than-normal-2-pointers

public class Solution {
    public boolean isSubsequence(String s, String t) {
        if (s == null || t == null) {
            return false;
        }
        else if (t.length() < s.length()) {
            return false;
        }
        else if (s.length() == 0) {
            return true;
        }
        
        int j = 0;
        char target = s.charAt(0);
        for (int i = 0; i < t.length(); i++) {
            char curr = t.charAt(i);
            if (curr == target) {
                j++;
                if (j >= s.length()) {
                    return true;
                }
                target = s.charAt(j);
            }
        }
        return false;
    }
}

reference:
https://discuss.leetcode.com/topic/57241/simple-java-code-with-explanation

public class Solution {
    public boolean isSubsequence(String s, String t) {
        if (s == null || t == null) {
            return false;
        }
        else if (t.length() < s.length()) {
            return false;
        }
        else if (s.length() == 0) {
            return true;
        }
        
        List<Integer>[] idx = new List[256];
        for (int i = 0; i < t.length(); i++) {
            char curr = t.charAt(i);
            if (idx[curr] == null) {
                idx[curr] = new ArrayList<Integer>();
            }
            idx[curr].add(i);
        }
        
        int pre = 0;
        for (int i = 0; i < s.length(); i++) {
            char curr = s.charAt(i);
            if (idx[curr] == null) {
                return false;
            }
            List<Integer> list = idx[curr];
            int index = Collections.binarySearch(list, pre);
            if (index < 0) {
                index = -index - 1;
            }
            if (index >= list.size()) {
                return false;
            }
            pre = list.get(index) + 1;
        }
        return true;
    }
}

reference:
https://discuss.leetcode.com/topic/58367/binary-search-solution-for-follow-up-with-detailed-comments

用三种不同的做法都写了下。其实都是 greedy思想的延伸。
前两个做法很相似。就是根据在t中找到s对应character 的index，然后一步步缩小搜索范围。

第三种做法其实也是这个原理，只不过用了binary search 来实现。每次搜索的时间是 O(log M), M = size of that sub list
可以说，接近于常数级操作。

介绍下 ，Collections.binarySearch 这个函数。
如果传入的list包含target，那就返回他的index
如果不包含，返回一个数， index which is < 0
我们做如下转换：
index = -index - 1;
就可以得到这个target如果插入list，应该插入的index

所以一开始pre = 0，如果0 这个index不在对应的list里面，那么就会返回 -1 => 转换得到0,
就代表，s中的这个character，应该对应于t中的index这个位置。
就是上面解法的 pre
然后一步步缩小范围。
其实也是 Greedy 思想的延伸。

Anyway, Good luck, Richardo! -- 09/20/2016