文章目录
一、思路
判断magazine中的字母能否组成ransomNote。
magazine中的字母可以比ransomNote多,所以我们对magazine中的字母简历哈希表
m
(
c
h
a
r
,
i
n
t
)
m(char,int)
m(char,int),然后ransomNote对
m
m
m查表,
m
m
m在相应位置减1,若果出现小于0的数,则不能构成。
PS:当ransomNote中出现了
m
m
m中不存在的值时,可以直接返回false。
二、代码
1.python
代码如下:
class Solution:
def canConstruct(self, ransomNote, magazine) :
dic = {}
for i in magazine:
dic[i] = dic.get(i,0) + 1
for j in ransomNote:
if j not in dic.keys():
return False
else:
dic[j] -= 1
for key,val in dic.items():
if val < 0:
return False
return True
2.C++
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
map<char,int> m;
for(int i=0;i<magazine.size();i++){
m[magazine[i]]++;
}
for(int j=0;j<ransomNote.size();j++){
if(m.find(ransomNote[j]) == m.end()){
return false;
}
else{
m[ransomNote[j]]--;
}
}
for(auto it=m.begin();it != m.end(); it++){
if(it->second < 0){
return false;
}
}
return true;
}
};