Leetcode-392. 判断子序列

392. 判断子序列
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

进阶：

如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

致谢：

特别感谢 @pbrother 添加此问题并且创建所有测试用例。

示例 1：

输入：s = "abc", t = "ahbgdc"
输出：true
示例 2：

输入：s = "axc", t = "ahbgdc"
输出：false

提示：

0 <= s.length <= 100
0 <= t.length <= 10^4
两个字符串都只由小写字符组成。

解题思路
利用HashMap+二分查找提供一种适合匹配很多个s的算法
1.我们先处理t，用map存储t中每个字母的下标
2.我们匹配s，在对应下标集中用二分查找到大于等于当前下标的值

class Solution {
    public boolean isSubsequence(String s, String t) {
        Map<Character,List<Integer>> map=new HashMap<>();
        //先预处理t
        for(int i=0;i<t.length();i++){
            char ch=t.charAt(i);
            if(!map.containsKey(ch)) map.put(ch,new ArrayList<>());
            List<Integer> list=map.get(ch);
            list.add(i);
            map.put(ch,list);
        }
        //从t的0坐标开始匹配
        int j=0;
        for(int i=0;i<s.length();i++){
            char c=s.charAt(i);
            if(map.containsKey(c)){
                List<Integer> list=map.get(c);
                int pos=left_bound(list,j);
                //没有比j大的
                if(pos>=list.size()) return false;
                j=list.get(pos)+1;
            }
            else{
                return false;
            }
        }
        return true;

    }
    //二分查找返回大于等于j的左边界
    public int left_bound(List<Integer> list,int j){
        int left=0;
        int right=list.size();
        while(left < right){
            int mid=left+(right-left)/2;
            if(list.get(mid) < j) left=mid+1;
            else right=mid;
        }
        return left;
    }
}