二分查找高效判定子序列

二分查找本身不难理解,难在巧妙地运用二分查找技巧。对于一个问题,你可能都很难想到它跟二分查找有关,比如前文 最长递增子序列 就借助一个纸牌游戏衍生出二分查找解法。

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

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

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

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

一、问题分析

首先,一个很简单的解法是这样的:

  1. bool isSubsequence(string s, string t) {
  2. int i = 0, j = 0;
  3. while (i < s.size() && j < t.size()) {
  4. if (s[i] == t[j]) i++;
  5. j++;
  6. }
  7. return i == s.size();
  8. }

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

gif

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

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

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

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

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

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

二、二分思路

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

  1. int m = s.length(), n = t.length();
  2. ArrayList<Integer>[] index = new ArrayList[256];
  3. // 先记下 t 中每个字符出现的位置
  4. for (int i = 0; i < n; i++) {
  5. char c = t.charAt(i);
  6. if (index[c] == null)
  7. index[c] = new ArrayList<>();
  8. index[c].add(i);
  9. }

二分查找高效判定子序列 - 图2

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

二分查找高效判定子序列 - 图3

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

二分查找高效判定子序列 - 图4

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

三、再谈二分查找

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

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

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

  1. // 查找左侧边界的二分查找
  2. int left_bound(ArrayList<Integer> arr, int tar) {
  3. int lo = 0, hi = arr.size();
  4. while (lo < hi) {
  5. int mid = lo + (hi - lo) / 2;
  6. if (tar > arr.get(mid)) {
  7. lo = mid + 1;
  8. } else {
  9. hi = mid;
  10. }
  11. }
  12. return lo;
  13. }

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

四、代码实现

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

  1. boolean isSubsequence(String s, String t) {
  2. int m = s.length(), n = t.length();
  3. // 对 t 进行预处理
  4. ArrayList<Integer>[] index = new ArrayList[256];
  5. for (int i = 0; i < n; i++) {
  6. char c = t.charAt(i);
  7. if (index[c] == null)
  8. index[c] = new ArrayList<>();
  9. index[c].add(i);
  10. }
  11. // 串 t 上的指针
  12. int j = 0;
  13. // 借助 index 查找 s[i]
  14. for (int i = 0; i < m; i++) {
  15. char c = s.charAt(i);
  16. // 整个 t 压根儿没有字符 c
  17. if (index[c] == null) return false;
  18. int pos = left_bound(index[c], j);
  19. // 二分搜索区间中没有找到字符 c
  20. if (pos == index[c].size()) return false;
  21. // 向前移动指针 j
  22. j = index[c].get(pos) + 1;
  23. }
  24. return true;
  25. }

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

二分查找高效判定子序列 - 图5

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

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

labuladong

上一篇:一行代码就能解决的算法题

下一篇:Linux的进程、线程、文件描述符是什么

目录