精选文章 LeetCode-Python-792. 匹配子序列的单词数(字符串 + 二分查找 + 哈希表)

LeetCode-Python-792. 匹配子序列的单词数(字符串 + 二分查找 + 哈希表)

作者:暴躁老哥在线刷题 时间: 2019-11-05 11:02:26
暴躁老哥在线刷题 2019-11-05 11:02:26

给定字符串 S 和单词字典 words, 求 words[i] 中是 S 的子序列的单词个数。

示例:
输入: 
S = "abcde"
words = ["a", "bb", "acd", "ace"]
输出: 3
解释: 有三个是 S 的子序列的单词: "a", "acd", "ace"。
注意:

所有在words和 S 里的单词都只由小写字母组成。
S 的长度在 [1, 50000]。
words 的长度在 [1, 5000]。
words[i]的长度在[1, 50]。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/number-of-matching-subsequences
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

 第一种思路:

麻瓜解,

对于words里每个单词,都用LeetCode-Python-392. 判断子序列(字符串 + 双指针)的方法处理一遍,

时间复杂度:O(len(S) * len(words))

空间复杂度:O(1)

比较麻瓜也比较简单,所以没有实现。

第二种思路:

每个word都要扫一遍 S 真的是太麻瓜了,这个时候考虑,空间换时间,

所以可以开一个哈希表,key是每个小写字母,val是一个list,里面【升序】存放所有这个小写字母在S里出现的下标。

这样对于每个word,只要能让其每个元素在S里出现的下标呈递增的趋势,则这个word就是S的子序列。

从贪心的角度出发,应该让word里每个元素取比它【前一个元素下标(pre)大的】最小的那个下标,

这个下标怎么找?

数组有序,暗示二分。

二分完如果存在合理的下标,就刷新pre, 然后继续处理剩下的元素,如果没有找到这样的下标,则说明这个word不行。

时间复杂度: O(len(S)+ len(words) * len(最长的word) * (log(S里最多的字母出现的频率)))

空间复杂度:O(len(S))

class Solution(object):
    def numMatchingSubseq(self, S, words):
        """
        :type S: str
        :type words: List[str]
        :rtype: int
        """
        from collections import defaultdict
        
        dic = defaultdict(list)
        for i, ch in enumerate(S): # 建哈希表
            dic[ch].append(i)
            
        res = 0
        for word in words:
            pre = -1
            flag = True
            for i, ch in enumerate(word):
                l = dic[ch]
                # 在l里找第一个比pre大的元素
                idx = bisect.bisect(l, pre)
                
                if idx == len(l):# 没找到
                    flag = False
                    break
                pre = l[idx]
                
            if flag:
                res += 1

        return res

 

勿删,copyright占位
分享文章到微博
分享文章到朋友圈

上一篇:LeetCode-922 按奇偶排序数组 II

下一篇:Docker组件

您可能感兴趣

  • 阿里面试最全面经总结

    1.听说你对JVM有点研究,讲一讲JVM的内存模型吧(我说虚拟机栈,本地方法栈,程序计数器,堆,方法区) 总的有什么,生命周期,每一个 JVM 的分区 ,线程私有,线程共享,直接内存 线程私有的生命周期和线程相同,线程共享的和虚拟机的生命周期相同。 java虚拟机栈是将方法的变量,出入口参数等以栈帧的形式存入,虚拟机中只有一个堆,堆中存入的是new出的对象,而且堆是垃圾回收的主要场所。方法区...

  • 渗透测试 QA 收集

    目录 1、拿到一个待检测的站,你觉得应该先做什么? 2、判断出网站的CMS对渗透有什么意义? 3.一个成熟并且相对安全的CMS,渗透时扫目录的意义? 4.常见的网站服务器容器。 5.mysql注入点,用工具对目标站直接写入一句话,需要哪些条件? 6.目前已知哪些版本的容器有解析漏洞,具体举例。 7.如何手工快速判断目标站是windows还是linux服务器? 8.为何一个mysql数据库的站...

  • Python 3.9 beta2 版本发布了,看看这 7 个新的 PEP 都是什么?

    点击上方“编程派”,选择设为“设为星标” 优质文章,第一时间送达! 原作:Jake Edge 译者:豌豆花下猫@Python猫 英文:https://lwn.net/Articles/819853 随着 Python 3.9.0b1 的发布,即开发周期中计划的四个 beta 版本的首个,Python 3.9 的功能已经是完善了。在 10 月发布最终版本之前,还会有许多测试和稳定性方面的工作要...

  • 算法之数据结构基础

    什么是数组?   数组对应的英文是array,是有限个相同类型的变量所组成的有序集合,数组中的每一个变量被称为元素。数组是最为简单、最为常用的数据结构。以整型数组为例,数组的存储形式如下图所示。   正如军队里的士兵存在编号一样,数组中的每一个元素也有着自己的下标,只不过这个下标从0开始,一直到数组长度-1。数组的另一个特点,是在内存中顺序存储,因此可以很好地实现逻辑上的顺序表。   数组在...

  • sql server 视图_轻松搜索SQL Server –搜索目录视图

    sql server 视图 The need to search through database schema for specific words or phrases is commonplace for any DBA. The ability to do so quickly, accurately, and completely is critical when developi...

  • sql2012 ssrs_如何使用SQL Server Reporting Services(SSRS)增强报告

    sql2012 ssrs 介绍 (Introduction) A few months ago, I was working on a few SQL Server reports for a client. The one request that I had received (from this client) was to ensure that the finished repor...

  • sql server 缓存_搜索SQL Server查询计划缓存

    sql server 缓存 Whenever a query is executed in SQL Server, its execution plan, as well as some useful execution data are placed into the plan cache for future use. This information is a treasure tro...

  • 基础概念:语言模型应用于检测

    2020/05/30 - 昨天的时候,简单学习了跟语言模型相关的内容。其实主要的内容都是word2vec的内容;本质上我想找的内容是,能够给我建立一个模糊的说法。我是使用这个模型,能带来的好处是什么。但是感觉上来说,完全就是从反向的角度来说明。使用了这个模型,然后告诉你这个模型的好处。 对于语言模型来说,我简单看了一下,这里来简单总结一下,不涉及具体原理。 首先就是最开始的one-hot模型...

华为云40多款云服务产品0元试用活动

免费套餐,马上领取!
CSDN

CSDN

中国开发者社区CSDN (Chinese Software Developer Network) 创立于1999年,致力为中国开发者提供知识传播、在线学习、职业发展等全生命周期服务。