每天一道编程题
题目描述
Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.
Each letter in the magazine string can only be used once in your ransom note.
题目大意:给定两个字符串,判断第一个字符串中的字符是否能够由第二个字符串中的字符组成(第二个字符串中的每个字符只能用一次)。样例只包含小写英文字母。
样例
canConstruct(“a”, “b”) -> false
canConstruct(“aa”, “ab”) -> false
canConstruct(“aa”, “aab”) -> true
python解法
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
if len(ransomNote) > len(magazine):return False
d = {}
for v in magazine:
if v in d:
d[v] += 1
else:
d[v] = 1
for v in ransomNote:
if v not in d or d[v] <= 0:
return False
else:
d[v] -= 1
return True
执行用时 :96 ms
内存消耗 :14 MB
题后反思:无
C语言解法
bool canConstruct(char * ransomNote, char * magazine){
int buckets[26] = {0};
int len = strlen(magazine);
int length = strlen(ransomNote);
if(len < length)
{
return false;
}
for (int i=0;i<len;i++)
{
buckets[magazine[i] - 'a'] ++;
}
for (int i=0;i<length;i++)
{
if (buckets[ransomNote[i]-'a']>0)
{
buckets[ransomNote[i]-'a'] --;
}
else
{
return false;
}
}
return true;
}
执行用时 :8 ms
内存消耗 :7.8 MB
题后反思:
- 因为只有小写字母,所以可以设置26个小桶,每个桶存一个字符,将magazine中出现的字符按照顺序存入桶中,然后检索ransomNote,不满足条件就可以返回false
文中都是我个人的理解,如有错误的地方欢迎下方评论告诉我,我及时更正,大家共同进步