[LeetCode]383. Ransom Note ★

每天一道编程题

题目描述

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
题后反思:

  1. 因为只有小写字母,所以可以设置26个小桶,每个桶存一个字符,将magazine中出现的字符按照顺序存入桶中,然后检索ransomNote,不满足条件就可以返回false

文中都是我个人的理解,如有错误的地方欢迎下方评论告诉我,我及时更正,大家共同进步

上一篇:11/2 上午


下一篇:383. Ransom Note