二分查找的妙用：判定子序列

来自公众号：labuladong预计阅读时间：6分钟二分查找本身不难理解，难在巧妙地运用二分查找技巧。对于一个问题，你可能都很难想到它跟二分查找有关，比如前文 最长递增子序列就借助一个纸牌游戏衍生出二分查找解法。今天再讲一道巧用二分查找的算法问题：如何判定字符串s是否是字符串t的子序列（可以假定s长度比较小，且t的长度非常大）。举两个例子：s = "abc", t = "ahbgdc", return true.s = "axc", t = "ahbgdc", return false.题目很容易理解，而且看起来很简单，但很难想到这个问题跟二分查找有关吧？一、问题分析首先，一个很简单的解法是这样的：bool isSubsequence(string s, string t) {    int i = 0, j = 0;    while (i         if (s[i] == t[j]) i++;        j++;     ………………………………