Keshawn_lu's Blog

Leetcode 792. 匹配子序列的单词数

二分查找
字数统计: 413阅读时长: 1 min
2022/11/17 Share

题目简介：

给定字符串 s 和字符串数组 words, 返回 words[i] 中是s的子序列的单词个数 。

字符串的 子序列 是从原始字符串中生成的新字符串，可以从中删去一些字符(可以是none)，而不改变其余字符的相对顺序。

  • 例如， “ace” 是 “abcde” 的子序列。

示例 1:

1
2
3
输入: s = "abcde", words = ["a","bb","acd","ace"]
输出: 3
解释: 有三个是 s 的子序列的单词: "a", "acd", "ace"。

提示:

  • 1 <= s.length <= 5 * 10^4
  • 1 <= words.length <= 5000
  • 1 <= words[i].length <= 50
  • words[i]和 s 都只由小写字母组成。

思路：

首先我们将s中所有字符的下标放至对应的位置，方便后续查找，即map[c]中放置的都是字符c的下标。

遍历每个word，用二分来查找每个字符的下标，若找不到，则说明不符合题意，舍去。

tip:

  • 利用引用减少时间复杂度

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    int numMatchingSubseq(string s, vector<string>& words) {

        vector<vector<int>> map(26, vector<int>());

        for(int i = 0; i < s.size(); i++){

            map[s[i] - 'a'].push_back(i);
        }

        int res = 0;
        for(auto& word : words){

            if(word.size() > s.size())
                continue;
            
            int begin = -1;
            int flag = 0;
            for(int i = 0; i < word.size(); i++){
                
                auto& now_map = map[word[i] - 'a']; //取引用很关键,减少时间
                auto j = upper_bound(now_map.begin(), now_map.end(), begin);	//寻找下一个比begin大的下标位置

                if(j == now_map.end()){	//找不到

                    flag = 1;
                    break;
                }

                begin = *j; 	//找到了，更新begin
            }

            if(flag == 0)
                res++;
        }

        return res;
    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网