LeetCode每日一题——792. 匹配子序列的单词数

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

题目

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

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

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

示例

示例 1:

输入: s = “abcde”, words = [“a”,“bb”,“acd”,“ace”]

输出: 3

解释: 有三个是 s的子序列的单词: “a”, “acd”, “ace”。

示例 2:

输入: s = “dsahjpjauf”, words = [“ahjpjau”,“ja”,“ahbwzgqnuk”,“tnmlanowax”]

输出: 2

提示:

1 <= s.length <= 5 * 104

1 <= words.length <= 5000

1 <= words[i].length <= 50

words[i]和 s 都只由小写字母组成。

思路

哈希表+二分查找:

传统的双指针判断是否为子序列的方法在本题会超时,思考一下,这里对字符不匹配的情况做了大量重复判断,所以采用哈希表记录下来

s中出现的字符的所有下标,在遍历words中的某个字符串word时,当我们遍历到word[i]的下一个字符word[i+1]时,我们不需要再依次从s往后匹配,我们只需要找到哈希表中键为word[i+1],值为大于i的最小值的坐标即为所求坐标(这一步骤可以使用二分查找)。

题解

class Solution:
    def numMatchingSubseq(self, s: str, words: List[str]) -> int:
      # 哈希表,存放s中字符与下标的映射
        dmap = {}
        for i, c in enumerate(s):
            if dmap.get(c):
                dmap[c].append(i)
            else:
                dmap[c] = [i]
        ans = 0
        # 遍历words
        for w in words:
          # 判断w中是否所有字符都符合规则
            ok = True
      # 判断的初始最小下标为-1
            idx = -1
            # 遍历words[i]
            for i in range(len(w)):
                idxs = dmap.get(w[i], [])
                # 二分查找
                l, r = 0, len(idxs) - 1
                while l < r :
                    mid = l + r >> 1
                    if dmap.get(w[i], [])[mid] > idx:
                        r = mid
                    else:
                        l = mid + 1
                # 未找到符合要求的下标
                if r < 0 or dmap.get(w[i], [])[r] <= idx:
                  # 判断条件为False,直接退出
                    ok = False
                    break
                # 找到符合要求的下标判断下标需要更改
                else:
                    idx = dmap.get(w[i], [])[r]
            # 若全部字符符合要求则+1,否则不变
            ans += 1 if ok else 0
        return ans
目录
相关文章
|
2天前
|
算法
【经典LeetCode算法题目专栏分类】【第3期】回溯问题系列:单词搜索、N皇后问题、判断有效数独、解数独
【经典LeetCode算法题目专栏分类】【第3期】回溯问题系列:单词搜索、N皇后问题、判断有效数独、解数独
|
4天前
|
存储
力扣-2904最短且字典序最小的美丽子序列
力扣-2904最短且字典序最小的美丽子序列
6 1
|
5天前
|
存储 算法 数据可视化
哈希表法快速求解最长连续序列 | 力扣128题详细解析
哈希表法快速求解最长连续序列 | 力扣128题详细解析
|
5天前
|
存储 自然语言处理 算法
LeetCode题目115:不同子序列
LeetCode题目115:不同子序列
|
5天前
|
数据采集 机器学习/深度学习 算法
力扣79题:单词搜索
力扣79题:单词搜索
|
5天前
|
存储 SQL 算法
LeetCode题58: 5种算法实现最后一个单词的长度【python】
LeetCode题58: 5种算法实现最后一个单词的长度【python】
|
5天前
|
存储 算法 数据挖掘
LeetCode 题目 30:串联所有单词的子串【python】
LeetCode 题目 30:串联所有单词的子串【python】
|
9天前
|
Java
贪心 -力扣860.柠檬水找零力扣2208.将数组和减半的最少操作次数力扣179.最大数力扣376.摆动序列
贪心 -力扣860.柠檬水找零力扣2208.将数组和减半的最少操作次数力扣179.最大数力扣376.摆动序列
|
9天前
|
算法 Java Go
【经典算法】LeetCode 392 判断子序列(Java/C/Python3/Go实现含注释说明,Easy)
【经典算法】LeetCode 392 判断子序列(Java/C/Python3/Go实现含注释说明,Easy)
14 0
|
9天前
|
算法 Java Go
【经典算法】LeetCode 58.最后一个单词的长度(Java/C/Python3/Go实现含注释说明,Easy)
【经典算法】LeetCode 58.最后一个单词的长度(Java/C/Python3/Go实现含注释说明,Easy)
11 0