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
• 两个字符串都只由小写字符组成。

贪心+快慢指针

class Solution {
    public boolean isSubsequence(String s, String t) {
        // 初始化两个指针 i 和 j，分别用于遍历字符串 s 和 t。判断 s 是否为 t 的子序列。
        // s为主，t为从。只有在t中找到s中对应的字符，才会移动s的指针。
        int i = 0, j = 0;
        
        // 使用 while 循环遍历字符串 t，同时检查字符串 s 中的字符
        while (i < s.length() && j < t.length()) {
            // 如果 s 和 t 中当前字符相等，s 的指针 i 向前移动。如果不相等，则s的指针不前进，t的指针继续前进。
            if (s.charAt(i) == t.charAt(j)) {
                i++;
            }
            // 不论字符是否相等，t 的指针 j 都向前移动。重点。
            j++;
        }
        
        // 判断是否遍历完 s 中的所有字符，如果是，说明 s 是 t 的子序列
        return i == s.length();
    }
}

• 时间复杂度：O(n+m)，其中 n 为 s 的长度，m 为 t 的长度。每次无论是匹配成功还是失败，都有至少一个指针发生右移，两指针能够位移的总距离为 n+m。
• 空间复杂度：O(1)。

如果给你一系列字符串 s1,s2,... 和字符串 t，你需要判定每个串 s 是否是 t 的子序列（可以假定 s 较短，t 很长）。

boolean[] isSubsequence(String[] sn, String t);

你也许会问，这不是很简单吗，还是刚才的逻辑，加个 for 循环不就行了？

可以，但是此解法处理每个 s 时间复杂度仍然是 O(m+n)，而如果巧妙运用二分查找，可以将时间复杂度降低，大约是 O(Klogm)。

哈希表，二分查找左边界，ValToIndex

利用哈希表直接定位数据，空间换时间。

比如对于这个情况，匹配了 "ab"，应该匹配 "c" 了：

按照之前的解法，我们需要 j 线性前进扫描字符 "c"，但借助 index 中记录的信息， 可以二分搜索 index[c] 中比 j 大的那个索引，在上图的例子中，就是在 [0,2,6] 中搜索比 4 大的那个索引：

这样就可以直接得到下一个 "c" 的索引。现在的问题就是，如何用二分查找计算那个恰好比 4 大的索引呢？答案是，寻找左侧边界的二分搜索就可以做到。

维护值到索引的映射。

对于搜索左侧边界的二分查找，有一个特殊性质：

当 val 不存在时，得到的索引恰好是比 val 大的最小元素索引。

什么意思呢，就是说如果在数组 [0,1,3,4] 中搜索元素 2，算法会返回索引 2，也就是元素 3 的位置，元素 3 是数组中大于 2 的最小元素。 所以我们可以利用二分搜索避免线性扫描。

class Solution {
    boolean isSubsequence(String s, String t) {
        int m = s.length(), n = t.length();
        
        // 对 t 进行预处理
        ArrayList<Integer>[] index = new ArrayList[26]; // 用于存储字符在 t 中出现的位置列表
        for (int i = 0; i < n; i++) {
            char c = t.charAt(i);
            if (index[c] == null) // 如果字符 c 还没有出现过
                index[c] = new ArrayList<>(); // 初始化位置列表
            index[c].add(i); // 将字符 c 出现的位置添加到位置列表中
        }

        // 串 t 上的指针
        int j = 0;
        // 借助 index 查找 s[i]。遍历s
        for (int i = 0; i < m; i++) {
            char c = s.charAt(i);
            
            // 如果字符 c 在 t 中没有出现过，返回 false
            if (index[c] == null) return false;
            // 在 t 中查找字符 c 的位置，要求位置大于等于 j，
            // 即在index[c]中查找索引大于等于j的c的位置的左边界，注意pos是链表index[c]的索引，
            // 不是t的索引，index[c].get(pos)才是t的索引。
            int pos = left_bound(index[c], j);
            // 二分搜索区间中没有找到字符 c
            if (pos == -1) return false;
            
            // 向前移动指针 j
            j = index[c].get(pos) + 1;
        }
        
        return true; // 如果所有字符都找到合适的位置，返回 true
    }

    // 查找左侧边界的二分查找
    int left_bound(ArrayList<Integer> arr, int target) {
        int left = 0, right = arr.size();
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (target > arr.get(mid)) {
                left = mid + 1; // 目标在右半部分
            } else {
                // 开区间和闭区间只是一个符号，本质是指定了搜索范围，
                // 所以只要明白下一轮搜索的元素有哪些，就能熟练地使用开区间和闭区间。这就是第一性原理。
                right = mid; // 目标在左半部分
            } 
        }
        
        // 如果没有找到合适的位置，返回 -1。重点。
        if (left == arr.size()) {
            return -1;
        }
        return left; // 返回左侧边界的位置
    }
}