二分查找高效判定子序列

数据结构精品课 已更新到 V2.1， 手把手刷二叉树系列课程 上线。

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode 力扣 难度
392. Is Subsequence 392. 判断子序列 🟢
792. Number of Matching Subsequences 792. 匹配子序列的单词数 🟠

———–

二分查找本身不难理解，难在巧妙地运用二分查找技巧。

对于一个问题，你可能都很难想到它跟二分查找有关，比如前文 最长递增子序列 就借助一个纸牌游戏衍生出二分查找解法。

今天再讲一道巧用二分查找的算法问题，力扣第 392 题「 判断子序列」：

请你判定字符串 s 是否是字符串 t 的子序列（可以假定 s 长度比较小，且 t 的长度非常大）。

举两个例子：

s = "abc", t = "**a**h**b**gd**c**", return true.

s = "axc", t = "ahbgdc", return false.

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

一、问题分析

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

boolean isSubsequence(String s, String t) {
    int i = 0, j = 0;
    while (i < s.length() && j < t.length()) {
        if (s.charAt(i) == t.charAt(j)) {
            i++;
        }
        j++;
    }
    return i == s.length();
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

bool isSubsequence(string s, string t) {
    int i = 0, j = 0;
    while (i < s.length() && j < t.length()) {
        if (s[i] == t[j]) {
            i++;
        }
        j++;
    }
    return i == s.length();
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

def isSubsequence(s: str, t: str) -> bool:
    i, j = 0, 0
    while i < len(s) and j < len(t):
        if s[i] == t[j]:
            i += 1
        j += 1
    return i == len(s)

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

func isSubsequence(s string, t string) bool {
    i, j := 0, 0
    for i < len(s) && j < len(t) {
        if s[i] == t[j] {
            i++
        }
        j++
    }
    return i == len(s)
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var isSubsequence = function(s, t) {
    let i = 0, j = 0;
    while (i < s.length && j < t.length) {
        if (s.charAt(i) == t.charAt(j)) {
            i++;
        }
        j++;
    }
    return i == s.length;
};
👾 代码可视化动画 👾

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

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

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

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

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

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

bool* isSubsequence(string *sn, string t);

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

def isSubsequence(sn: List[str], t: str) -> List[bool]:

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

func isSubsequence(sn []string, t string) []bool {
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var isSubsequence = function(sn, t) {
    var n = t.length();
    var dp = new boolean[n+1];
    dp[0] = true;

    for (var s : sn) {
        for (var i = n; i >= 0; i--) {
            if (i == 0) {
                dp[i] = false;
            }
            else if (t.charAt(i-1) == s.charAt(0)) {
                dp[i] = dp[i-1] || dp[i];
            }
        }
    }

    return dp[n];
};

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

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

二、二分思路

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

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

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

int m = s.length(), n = t.length();
vector<vector<int>> index(256, vector<int>());
// 先记下 t 中每个字符出现的位置
for (int i = 0; i < n; i++) {
    char c = t[i];
    index[c].push_back(i);
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

m, n = len(s), len(t)
index = [[] for _ in range(256)]
# 先記下 t 中每個字符出現的位置
for i in range(n):
    c = t[i]
    if index[ord(c)] is None:
        index[ord(c)] = []
    index[ord(c)].append(i)

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

m, n := len(s), len(t)
index := make([][]int, 256) // declare a slice of 256 empty slices of ints
// 先记下 t 中每个字符出现的位置
for i := 0; i < n; i++ {
    c := t[i]
    if index[c] == nil {
        index[c] = []int{}
    }
    index[c] = append(index[c], i)
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

// 使用 var 定义函数
var m = s.length, n = t.length;
var index = new Array(256);
// 先记下 t 中每个字符出现的位置
for (var i = 0; i < n; i++) {
    var c = t.charAt(i);
    if (index[c] == null) {
        index[c] = new Array();
    }
    index[c].push(i);
}

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

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

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

三、再谈二分查找

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

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

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

// 查找左侧边界的二分查找
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;
        } 
    }
    if (left == arr.size()) {
        return -1;
    }
    return left;
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

// 查找左侧边界的二分查找
int left_bound(vector<int>& arr, int target) { 
    int left = 0, right = arr.size(); 
    while (left < right) { 
        int mid = left + (right - left) / 2; // 计算中间位置索引
        if (target > arr[mid]) { // 目标值大于中间位置的值时，搜索区间变为 [mid + 1, right]
            left = mid + 1; 
        } else { // 目标值小于等于中间位置的值时，搜索区间变为 [left, mid]
            right = mid; 
        } 
    } 
    if (left == arr.size()) { // 当 left 等于数组长度时，说明所有数都小于目标值，返回 -1
        return -1;
    }
    return left; // 返回目标值的左侧边界
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

# 查找左侧边界的二分查找
def left_bound(arr: list[int], target: int) -> int:
    left = 0
    right = len(arr)
    
    while left < right:
        mid = left + (right - left) // 2
        if target > arr[mid]:
            left = mid + 1
        else:
            right = mid
            
    if left == len(arr):
        return -1
        
    return left

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

// 查找左侧边界的二分查找
func leftBound(arr []int, target int) int {
    left, right := 0, len(arr)
    for left < right {
        mid := left + (right - left) / 2
        if target > arr[mid] {
            left = mid + 1
        } else {
            right = mid
        } 
    }
    if left == len(arr) {
        return -1
    }
    return left
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

// 查找左侧边界的二分查找
var left_bound = function(arr, target) {
    var left = 0, right = arr.length;
    while (left < right) {
        var mid = left + Math.floor((right - left) / 2);
        if (target > arr[mid]) {
            left = mid + 1;
        } else {
            right = mid;
        } 
    }
    // 如果 left 越界 或者 left 对应的值不等于 target，说明数组中不存在 target
    if (left == arr.length || arr[left] != target) {
        return -1;
    }
    return left;
}

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

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

boolean isSubsequence(String s, String t) {
    int m = s.length(), n = t.length();
    // 对 t 进行预处理
    ArrayList<Integer>[] index = new ArrayList[256];
    for (int i = 0; i < n; i++) {
        char c = t.charAt(i);
        if (index[c] == null) 
            index[c] = new ArrayList<>();
        index[c].add(i);
    }
    
    // 串 t 上的指针
    int j = 0;
    // 借助 index 查找 s[i]
    for (int i = 0; i < m; i++) {
        char c = s.charAt(i);
        // 整个 t 压根儿没有字符 c
        if (index[c] == null) return false;
        int pos = left_bound(index[c], j);
        // 二分搜索区间中没有找到字符 c
        if (pos == -1) return false;
        // 向前移动指针 j
        j = index[c].get(pos) + 1;
    }
    return true;
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

bool isSubsequence(string s, string t) {
    int m = s.length(), n = t.length();
    // 对 t 进行预处理
    vector<vector<int>> index(256);
    for (int i = 0; i < n; i++) {
        char c = t.at(i);
        index[c].push_back(i);
    }
    
    // 串 t 上的指针
    int j = 0;
    // 借助 index 查找 s[i]
    for (int i = 0; i < m; i++) {
        char c = s.at(i);
        // 整个 t 压根儿没有字符 c
        if (index[c].empty()) return false;
        auto iter = lower_bound(index[c].begin(), index[c].end(), j);
        // 二分搜索区间中没有找到字符 c
        if (iter == index[c].end()) return false;
        // 向前移动指针 j
        j = *iter + 1;
    }
    return true;
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

from typing import List

def isSubsequence(s: str, t: str) -> bool:
    m, n = len(s), len(t)
    # 对 t 进行预处理
    index = [[] for _ in range(256)]
    for i in range(n):
        c = t[i]
        if index[ord(c)] == None:
            index[ord(c)] = []
        index[ord(c)].append(i)
    
    # 串 t 上的指针
    j = 0
    # 借助 index 查找 s[i]
    for i in range(m):
        c = s[i]
        # 整个 t 压根儿没有字符 c
        if not index[ord(c)]:
            return False
        pos = left_bound(index[ord(c)], j)
        # 二分搜索区间中没有找到字符 c
        if pos == -1:
            return False
        # 向前移动指针 j
        j = index[ord(c)][pos] + 1
    return True


def left_bound(nums: List[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return left if left < len(nums) and nums[left] >= target else -1

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

func isSubsequence(s string, t string) bool {
    m, n := len(s), len(t)
    // 对 t 进行预处理
    index := make([][]int, 256)
    for i := 0; i < n; i++ {
        c := t[i]
        if index[c] == nil {
            index[c] = make([]int, 0)
        }
        index[c] = append(index[c], i)
    }
    
    // 串 t 上的指针
    j := 0
    // 借助 index 查找 s[i]
    for i := 0; i < m; i++ {
        c := s[i]
        // 整个 t 压根儿没有字符 c
        if index[c] == nil {
            return false
        }
        pos := left_bound(index[c], j)
        // 二分搜索区间中没有找到字符 c
        if pos == -1 {
            return false
        }
        // 向前移动指针 j
        j = index[c][pos] + 1
    }
    return true
}

func left_bound(nums []int, target int) int {
    left, right := 0, len(nums) - 1
    for left <= right {
        mid := left + (right - left) / 2
        if nums[mid] >= target {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    if left != len(nums) && nums[left] >= target {
        return left
    }
    return -1
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var isSubsequence = function(s, t) {
    var m = s.length, n = t.length;
    // 对 t 进行预处理
    var index = new Array(256);
    for (var i = 0; i < n; i++) {
        var c = t.charAt(i);
        if (index[c.charCodeAt()] == null) 
            index[c.charCodeAt()] = new Array();
        index[c.charCodeAt()].push(i);
    }
    
    // 串 t 上的指针
    var j = 0;
    // 借助 index 查找 s[i]
    for (var i = 0; i < m; i++) {
        var c = s.charAt(i);
        // 整个 t 压根儿没有字符 c
        if (index[c.charCodeAt()] == null) return false;
        var pos = left_bound(index[c.charCodeAt()], j);
        // 二分搜索区间中没有找到字符 c
        if (pos == -1) return false;
        // 向前移动指针 j
        j = index[c.charCodeAt()][pos] + 1;
    }
    return true;
};

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

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

明白了这个思路，我们可以直接拿下力扣第 792 题「 匹配子序列的单词数」：给你输入一个字符串列表 words 和一个字符串 s，问你 words 中有多少字符串是 s 的子序列。

函数签名如下：

int numMatchingSubseq(String s, String[] words)

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

int numMatchingSubseq(string s, vector<string>& words)

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

def numMatchingSubseq(s: str, words: List[str]) -> int

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

func numMatchingSubseq(s string, words []string) int {

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var numMatchingSubseq = function(s, words) {
    // function body here...
}

我们直接把上一道题的代码稍微改改即可完成这道题：

int numMatchingSubseq(String s, String[] words) {
    // 对 s 进行预处理
    // char -> 该 char 的索引列表
    ArrayList<Integer>[] index = new ArrayList[256];
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (index[c] == null) {
            index[c] = new ArrayList<>();
        }
        index[c].add(i);
    }
    
    int res = 0;
    for (String word : words) {
        // 字符串 word 上的指针
        int i = 0;
        // 串 s 上的指针
        int j = 0;
        // 借助 index 查找 word 中每个字符的索引
        for (; i < word.length(); i++) {
            char c = word.charAt(i);
            // 整个 s 压根儿没有字符 c
            if (index[c] == null) {
                break;
            }
            int pos = left_bound(index[c], j);
            // 二分搜索区间中没有找到字符 c
            if (pos == -1) {
                break;
            }
            // 向前移动指针 j
            j = index[c].get(pos) + 1;
        }
        // 如果 word 完成匹配，则是子序列
        if (i == word.length()) {
            res++;
        }
    }
    
    return res;
}

// 查找左侧边界的二分查找
int left_bound(ArrayList<Integer> arr, int target) {
    // 见上文
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

int numMatchingSubseq(string s, vector<string>& words) {
    // 对 s 进行预处理
    // char -> 该 char 的索引列表
    vector<vector<int>> index(256);
    for (int i = 0; i < s.length(); i++) {
        char c = s[i];
        index[c].push_back(i);
    }

    int res = 0;
    for (string word : words) {
        // 字符串 word 上的指针
        int i = 0;
        // 串 s 上的指针
        int j = 0;
        // 借助 index 查找 word 中每个字符的索引
        for (; i < word.size(); i++) {
            char c = word[i];
            // 整个 s 压根儿没有字符 c
            if (index[c].empty()) {
                break;
            }
            auto it = lower_bound(index[c].begin(), index[c].end(), j);
            // 二分搜索区间中没有找到字符 c
            if (it == index[c].end()) {
                break;
            }
            // 向前移动指针 j
            j = *it + 1;
        }
        // 如果 word 完成匹配，则是子序列
        if (i == word.size()) {
            res++;
        }
    }
    return res;
}

// 查找左侧边界的二分查找
int left_bound(vector<int>& arr, int target) {
    // 见上文
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

from typing import List

def numMatchingSubseq(s: str, words: List[str]) -> int:
    # 对 s 进行预处理，记录字符 c 的所有出现位置
    index = [[] for _ in range(256)]
    for i in range(len(s)):
        c = ord(s[i]) # 获取s中指定下标的字符及其ascll码值
        if index[c] == None:
            # 如果第一次出现，则初始化一个空列表
            index[c] = []
        index[c].append(i) # 添加位置信息
    
    # 统计符合要求的 words
    res = 0 # 记录符合要求的单词数量
    for word in words: # 遍历单词列表
        i = 0 # 记录已匹配的单词长度
        j = 0 # 指向 s 中当前查找的字符的位置
        for i in range(len(word)): # 遍历单词中的字符
            c = ord(word[i]) # 获取单词当前字符及其ascll码值
            # 如果 s 中不存在单词当前字符，则不可能匹配
            if not index[c]:
                break
            pos = bisect_left(index[c], j) # 二分查找 c 第一次出现的位置
            # 如果没找到，则已经匹配失败了
            if pos == len(index[c]):
                break
            j = index[c][pos] + 1 # pos 是下标，所以要加1，指向下一个位置
        if i == len(word):
            # 如果整个单词匹配结束，说明这是一个符合要求的单词
            res += 1
    
    # 返回符合要求的单词数量
    return res

def left_bound(arr: List[int], target: int) -> int:
    # 查找左侧边界的二分查找
    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    return -1 if left == len(arr) or arr[left] != target else left

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

func numMatchingSubseq(s string, words []string) int {
    index := make([][]int, 256)
    for i := 0; i < len(s); i++ {
        c := s[i]
        if index[c] == nil {
            index[c] = make([]int, 0)
        }
        index[c] = append(index[c], i)
    }
    
    res := 0
    for _, word := range words {
        i := 0
        j := 0
        for ; i < len(word); i++ {
            c := word[i]
            if index[c] == nil {
                break
            }
            pos := leftBound(index[c], j)
            if pos == -1 {
                break
            }
            j = index[c][pos] + 1
        }
        if i == len(word) {
            res++
        }
    }
    
    return res
}

func leftBound(arr []int, target int) int {
    // 见上文
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var numMatchingSubseq = function(s, words) {
    // 对 s 进行预处理
    // char -> 该 char 的索引列表
    const index = new Array(256);
    for (let i = 0; i < s.length; i++) {
        const c = s.charAt(i);
        if (index[c.charCodeAt(0)] == null) {
            index[c.charCodeAt(0)] = new Array();
        }
        index[c.charCodeAt(0)].push(i);
    }
    
    let res = 0;
    for (let i = 0; i < words.length; i++) {
        const word = words[i];
        // 字符串 word 上的指针
        let j = 0;
        // 串 s 上的指针
        let k = 0;
        // 借助 index 查找 word 中每个字符的索引
        for (; j < word.length; j++) {
            const c = word.charAt(j);
            // 整个 s 压根儿没有字符 c
            if (index[c.charCodeAt(0)] == null) {
                break;
            }
            const pos = left_bound(index[c.charCodeAt(0)], k);
            // 二分搜索区间中没有找到字符 c
            if (pos == -1) {
                break;
            }
            // 向前移动指针 k
            k = index[c.charCodeAt(0)][pos] + 1;
        }
        // 如果 word 完成匹配，则是子序列
        if (j == word.length) {
            res++;
        }
    }
    
    return res;
}

// 查找左侧边界的二分查找
var left_bound = function(arr, target) {
    let left = 0, right = arr.length - 1;
    while (left <= right) {
        const mid = (right - left) / 2 + left;
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return left < arr.length ? left : -1;
}

＿＿＿＿＿＿＿＿＿＿＿＿＿

《labuladong 的算法小抄》已经出版，关注公众号查看详情；后台回复关键词「进群」可加入算法群；回复「全家桶」可下载配套 PDF 和刷题全家桶：

共同维护高质量学习环境，评论礼仪见这里，违者直接拉黑不解释