792. Number of Matching Subseque

792. Number of Matching Subsequences
793. Longest Word in Dictionary through Deleting
     这两道题一起来总结一下。
     把它们放在一起，是因为他俩几乎是同一道题。
     都是找一个单词是不是另外一个单词的subsequence.
     如果只找一次的话，用双指针做一下就好了。
     如果像792和524那样要找很多次，为了加速优化如下。
     把母单词的letter统计一下，每个letter记下他出现的位置，记在一个List<Integer>里面。然后要有 26个这样的List<Integer>
     对于子单词，用一个指针从左到右。假设第一个字母是b， 我就去找到母单词的b对应的List<Integer>找到他第一个出现的位置， 假设是 3， 我记下来。下一个字母假设是C， 我就去母单词c对应的List<Integer>里找c在3之后第一次出现的位置。这时可以用二分查找加速。
     时间复杂度，我想了一下，就没在这里写了，需要做假设再讨论。

这题容易出错的点：

1. List[] locations = new ArrayList[26]; 这是对的。
   如果要建 Array of List, 请用这种形式。
   List<Integer>[] locations = new ArrayList<Integer>[26]; 这是错的。
   List<Integer>[] locations = new ArrayList<>[26]; 这也是错的
   List<Integer>[] locations = new ArrayList[26]; 这也是对的
   总之后面的ArrayList那里什么也不要多写。
2. 这题在binarySearch的时候，有两个index的概念，一个是List<Integer>里面的index, 一个List<Integer>里面的value, 恰恰这个value也是index，是母单词字母的index， 非常容易搞混。特别特别小心。

代码
先贴524的。

public String findLongestWord(String s, List<String> d) {
        String ans = "";
        List[] counts = new ArrayList[26];
        for (int i = 0; i < 26; i++) {
            counts[i] = new ArrayList<>();
        }
        for (int i = 0; i < s.length(); i++) {
            counts[s.charAt(i) - 'a'].add(i);
        }
        for (String w : d) {
            if (w.length() < ans.length()) continue;
            if (contains(counts, w)) {
                if (w.length() > ans.length() || (w.compareTo(ans) < 0))
                ans = w;
            }
        }
        return ans;
    }
    private boolean contains(List[] counts, String w) {
        int pt = -1;
        for (char c : w.toCharArray()) {
            pt = binarySearch(counts[c - 'a'], pt + 1);
            if (pt == -1) return false;
        }
        return true;
    }
    private int binarySearch(List<Integer> list, int target) {
        if (list.size() == 0 ) return -1;
        int l = 0, r = list.size() - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            int midVal = list.get(mid);
            if (midVal == target) return midVal;
            if (midVal < target) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        if (list.get(l) >= target) return list.get(l);
        return -1;
    }

再贴 792的

public int numMatchingSubseq(String S, String[] words) {
        List[] locations = new ArrayList[26];
        for (int i = 0; i < 26; i++) {
            locations[i] = new ArrayList<Integer>();
        }
        for (int i = 0; i < S.length(); i++) {
            locations[S.charAt(i) - 'a'].add(i);
        }
        int count = 0;
        for (String w : words) {
            if (contains(locations, w)) count++;
        }
        return count;
    }
    private boolean contains(List[] locations, String w) {
        int pt = -1;
        for (char c : w.toCharArray()) {
            pt = findNext(locations[c - 'a'], pt + 1);
            if (pt == -1) return false;
        }
        return true;
    }
    private int findNext(List<Integer> indexes, int left) {
        if (indexes.size() == 0) return -1;
        int l = 0, r = indexes.size() - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            int midPos = indexes.get(mid);
            if (midPos == left) return left;
            if (midPos < left) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        if (indexes.get(r) >= left ) return indexes.get(r);
        return -1;
    }