题目描述
给你一份『词汇表』(字符串数组) words 和一张『字母表』(字符串) chars。
假如你可以用 chars 中的『字母』(字符)拼写出 words 中的某个『单词』(字符串),那么我们就认为你掌握了这个单词。
注意:每次拼写(指拼写词汇表中的一个单词)时,chars 中的每个字母都只能用一次。
返回词汇表 words 中你掌握的所有单词的 长度之和。
示例 1:
输入:words = ["cat","bt","hat","tree"], chars = "atach"
输出:6
解释:
可以形成字符串 "cat" 和 "hat",所以答案是 3 + 3 = 6。
示例 2:
输入:words = ["hello","world","leetcode"], chars = "welldonehoneyr"
输出:10
解释:
可以形成字符串 "hello" 和 "world",所以答案是 5 + 5 = 10。
提示:
- 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;
}
运行结果
提交代码(利用数组优化)
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;
}
运行结果
题目来源
标签:map,string,int,chars,50,char,words,字符串,unordered From: https://blog.51cto.com/u_15939722/6004144来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/find-words-that-can-be-formed-by-characters