Daily LeetCode – day0111 0792. Number of Matching Subsequences

import java.util.ArrayList;
import java.util.List;

// 0792. Number of Matching Subsequences
class Solution {
    public int numMatchingSubseq(String s, String[] words) {
        char[] charArray = s.toCharArray();
        int len = charArray.length;
        List<List<Integer>> charsIndexes = new ArrayList<>();
        for (int i = 0; i < 123; ++i) {
            charsIndexes.add(new ArrayList<>());
        }
        for (int i = 0; i < len; ++i) {
            charsIndexes.get(charArray[i]).add(i);
        }
        int ans = 0;
        for (String word : words) {
            ans += isMatching(word, charsIndexes);
        }
        return ans;
    }

    private int isMatching(String word, List<List<Integer>> charsIndexes) {
        int preIndex = -1;
        for (char c : word.toCharArray()) {
            List<Integer> charIndexes = charsIndexes.get(c);
            if (charIndexes.size() == 0) {
                return 0;
            }
            int currentIndex = binarySearch(preIndex, charIndexes);
            if (currentIndex <= preIndex) {
                return 0;
            }
            preIndex = currentIndex;
        }
        return 1;
    }

    private int binarySearch(int preIndex, List<Integer> charIndexes) {
        int left = 0;
        int right = charIndexes.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (charIndexes.get(mid) <= preIndex) {
                left = mid + 1;
            } else{
                right = mid;
            }
        }
        return charIndexes.get(left);
    }
}

学习笔记：
如果要你判断一个字符串是不是另一个字符串的子序列，其实可以使用双指针算法。
那么多个字符串是不是字符串s的子序列呢？理所当然想到循环呗。
结果这题目就是不让循环通过的。
所以得用巧办法了。
记录每种字母出现的索引。
然后遍历每个字符串的时候，去找可能出现的最左的那个字母索引。
所以这里也用到了二分搜索，是二分搜索中的搜索左边界。