美文网首页
LeetCode 383. Ransom Note

LeetCode 383. Ransom Note

作者: njim3 | 来源:发表于2019-01-31 15:08 被阅读0次

    题目

    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.
    Note:
    You may assume that both strings contain only lowercase letters.

    canConstruct("a", "b") -> false
    canConstruct("aa", "ab") -> false
    canConstruct("aa", "aab") -> true
    

    解析

    此题难度不大,主要是考虑如何能在较短的时间内完成,双层循环或者排序后循环都会造成Time limit exceeded。因此可以采用映射的方式来对所出现的字母次数进行统计,这样可以达到O(n)的时间复杂度。
    由于C语言中没有类似于python中的dict类型,在之前题目中提到过,实现这种dict可以使用数组映射的方式,dictArr[x - 'a']这种方式。

    代码(C语言)

    bool canConstruct(char* ransomNote, char* magazine) {
        int* countArr = (int*)calloc(26, sizeof(int));
        int count = 0;
        int ransomSize = (int)strlen(ransomNote);
        int magzaineSize = (int)strlen(magazine);
        
        for (int i = 0; i < ransomSize; ++i) {
            ++countArr[ransomNote[i] - 'a'];
            
            ++count;
        }
        
        for (int i = 0; i < magzaineSize && count > 0; ++i) {
            if (countArr[magazine[i] - 'a'] > 0) {
                --countArr[magazine[i] - 'a'];
                
                --count;
            }
        }
        
        free(countArr);
        
        if (count)
            return false;
        
        return true;
    }
    

    需要说明的是,strlen()耗时较多,因此如果将其放到循环中,每次循环都要计算其值,耗时较长,这样也会发生超时错误。
    另外一点,最后count不为0,即应该return false,而不是单纯的count > 0。此处需要读者思考一下。

    相关文章

      网友评论

          本文标题:LeetCode 383. Ransom Note

          本文链接:https://www.haomeiwen.com/subject/sxkksqtx.html