数据结构精品课 已更新到 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 和刷题全家桶:
共同维护高质量学习环境,评论礼仪见这里,违者直接拉黑不解释