LeetCode题解(1160):判断可由指定字母拼写的所有单词总长(Python)
发布日期:2021-06-29 19:55:29
浏览次数:3
分类:技术文章
本文共 1425 字,大约阅读时间需要 4 分钟。
题目:(简单)
解法 | 时间复杂度 | 空间复杂度 | 执行用时 |
---|---|---|---|
Ans 1 (Python) | O ( N × K + C ) O(N×K+C) O(N×K+C) : K为单词平均长度,C为chars长度 | O ( C ) O(C) O(C) : C为chars的长度 | 400ms (9.72%) |
Ans 2 (Python) | O ( N × K + C ) O(N×K+C) O(N×K+C) : K为单词平均长度,C为chars长度 | O ( C ) O(C) O(C) : C为chars的长度 | 196ms (60.88%) |
Ans 3 (Python) | O ( N × K + C ) O(N×K+C) O(N×K+C) : K为单词平均长度,C为chars长度 | O ( C ) O(C) O(C) : C为chars的长度 | 104ms (98.39%) |
LeetCode的Python执行用时随缘,只要时间复杂度没有明显差异,执行用时一般都在同一个量级,仅作参考意义。
解法一(使用collections.Counter类):
def countCharacters(self, words: List[str], chars: str) -> int: pattern = collections.Counter(chars) ans = 0 for word in words: count = pattern & collections.Counter(word) if len(list(count.elements())) == len(word): ans += len(word) return ans
解法二(哈希表计数):
def countCharacters(self, words: List[str], chars: str) -> int: pattern = collections.Counter(chars) ans = 0 for word in words: count = pattern.copy() for c in word: if c not in count or count[c] <= 0: break else: count[c] -= 1 else: ans += len(word) return ans
解法三(更好的哈希表计数):
def countCharacters(self, words: List[str], chars: str) -> int: pattern = collections.Counter(chars) ans = 0 for word in words: for c in word: if c not in pattern or word.count(c) > pattern[c]: break else: ans += len(word) return ans
转载地址:https://dataartist.blog.csdn.net/article/details/107108025 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
感谢大佬
[***.8.128.20]2024年05月03日 06时01分39秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
嵌入式Linux系统移植-使用crosstool创建自己的交叉编译器
2019-04-30
编译binutil包
2019-04-30
使用Qt作窗口截屏
2019-04-30
grep与命令混合的用法
2019-04-30
Shell编程基础
2019-04-30
linux telnet命令参数及用法详解--telnet连接远程终端命令
2019-04-30
怎样查看rpm安装包的安装路径
2019-04-30
RedHat Linux下FTP服务配置
2019-04-30
shell检查网络出现异常、僵尸进程、内存过低后机器自动重启
2019-04-30
利用shell脚本来监控linux系统的内存
2019-04-30
常用awk命令
2019-04-30
Qt使用一张图片上的众多icon作为控件图标
2019-04-30
QT拖拽功能简介
2019-04-30
Qt拖放
2019-04-30
Qt图片拖放
2019-04-30
android库模块直接依赖时不能重复嵌套依赖
2019-04-30
关于SDK回调Qt函数的问题
2019-04-30
查询linux系统中空闲内存/内存使用状态查看/剩余内存查看
2019-04-30
Linux下屏保设置
2019-04-30
使用开源软件OpenIPMI来监控服务器温度
2019-04-30