LeetCode刷题(50)~拼写单词【利用数组替换map/unordered_map 提高效率】
【摘要】 题目描述
给你一份『词汇表』(字符串数组) words 和一张『字母表』(字符串) chars。
假如你可以用 chars 中的『字母』(字符)拼写出 words 中的某个『单词』(字符串),那么我们就认为你掌握了这个单词。
注意:每次拼写(指拼写词汇表中的一个单词)时,chars 中的每个字母都只能用一次。
返回词汇表 words 中你掌握的所有单词的 长度之...
题目描述
给你一份『词汇表』(字符串数组) words 和一张『字母表』(字符串) chars。
假如你可以用 chars 中的『字母』(字符)拼写出 words 中的某个『单词』(字符串),那么我们就认为你掌握了这个单词。
注意:每次拼写(指拼写词汇表中的一个单词)时,chars 中的每个字母都只能用一次。
返回词汇表 words 中你掌握的所有单词的 长度之和。
示例 1:
输入:words = ["cat","bt","hat","tree"], chars = "atach"
输出:6
解释:
可以形成字符串 "cat" 和 "hat",所以答案是 3 + 3 = 6。
- 1
- 2
- 3
- 4
示例 2:
输入:words = ["hello","world","leetcode"], chars = "welldonehoneyr"
输出:10
解释:
可以形成字符串 "hello" 和 "world",所以答案是 5 + 5 = 10。
- 1
- 2
- 3
- 4
提示:
- 1 <= words.length <= 1000
- 1 <= words[i].length, chars.length <= 100
- 所有字符串中都仅包含小写英文字母
解答 By 海轰
提交代码(暴力解法)
bool isword(string a,string b) { unordered_map<char,int> m; for(char c:b) ++m[c]; for(char c:a) { if(m.find(c)==m.end()||m[c]<=0) return false; else { --m[c]; } } return true; } int countCharacters(vector<string>& words, string chars) { int len=words.size(); int count=0; for(int i=0;i<len;++i) if(isword(words[i],chars)==true) count+=words[i].length(); return count; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
运行结果
提交代码(利用数组优化)
int countCharacters(vector<string>& words, string chars) { char a[26]={0}; for(char c:chars) ++a[c-'a']; int result=0; for(string word:words) { char b[26]={0}; for(char c:word) ++b[c-'a']; int i; for(i=0;i<26;++i) { if(a[i]<b[i]) break; } if(i==26) result+=word.length(); else result+=0; } return result; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
运行结果
题目来源
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/find-words-that-can-be-formed-by-characters
文章来源: haihong.blog.csdn.net,作者:海轰Pro,版权归原作者所有,如需转载,请联系作者。
原文链接:haihong.blog.csdn.net/article/details/108021838
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)