二分查找高效判定子序列

今天再讲一道巧用二分查找的算法问题：如何判定字符串是否是字符串 t 的子序列（可以假定 s 长度比较小，且 t 的长度非常大）。举两个例子：

s = “abc”, t = “ahbgdc“, return true.

s = “axc”, t = “ahbgdc”, return false.

题目很容易理解，而且看起来很简单，但很难想到这个问题跟二分查找有关吧？

首先，一个很简单的解法是这样的：

其思路也非常简单，利用双指针 i, j 分别指向 s, t，一边前进一边匹配子序列：

读者也许会问，这不就是最优解法了吗，时间复杂度只需 O(N)，N 为 t 的长度。

是的，如果仅仅是这个问题，这个解法就够好了，不过这个问题还有 follow up：

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

可以，但是此解法处理每个 s 时间复杂度仍然是 O(N)，而如果巧妙运用二分查找，可以将时间复杂度降低，大约是 O(MlogN)。由于 N 相对 M 大很多，所以后者效率会更高。

二分思路主要是对 t 进行预处理，用一个字典 index 将每个字符出现的索引位置按顺序存储下来：

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

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

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

在前文二分查找详解中，详解了如何正确写出三种二分查找算法的细节。二分查找返回目标值 val 的索引，对于搜索左侧边界的二分查找，有一个特殊性质：

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

以上就是搜索左侧边界的二分查找，等会儿会用到，其中的细节可以参见前文《二分查找详解》，这里不再赘述。

这里以单个字符串为例，对于多个字符串 s，可以把预处理部分抽出来。

算法执行的过程是这样的：

可见借助二分查找，算法的效率是可以大幅提升的。

坚持原创高质量文章，致力于把算法问题讲清楚，欢迎关注我的公众号 labuladong 获取最新文章：