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.

Note:

You may assume that both strings contain only lowercase letters.

canConstruct("a", "b") -> false

canConstruct("aa", "ab") -> false

canConstruct("aa", "aab") -> true

题目大意:ransom Note构成一个字符串,magazines构成一个字符串,对于ransom Note字符串,能否由magazines中的字符构成,其中magazines中的每个字符只能使用一次。

思路:

1.ransomNote.length > magazines.length 显然,ransomNote不能由magazines构成

2.ransomNote中出现的每一个字符进行统计,统计其出现次数,对magazines中的字符也进行同样的统计。对每一个相同字符,ransomNote中出现的次数小于等于magazines中出现的次数时, ransomNote可由magazines构成

代码:

class Solution(object):
def canConstruct(self, ransomNote, magazine):
    """
    :type ransomNote: str
    :type magazine: str
    :rtype: bool
    """
    if len(ransomNote) > len(magazine):
        return False

    a = dict()
    b = dict()

    for i in range(len(ransomNote)):
        a[ord(ransomNote[i]) - ord('a')] = 0
    for x in range(len(magazine)):
        b[ord(magazine[x]) - ord('a')] = 0

    for i in range(len(ransomNote)):
        a[ord(ransomNote[i]) - ord('a')] +=1

    for x in range(len(magazine)):
        b[ord(magazine[x]) - ord('a')] +=1

    for i in range(len(ransomNote)):
        if b.has_key(ord(ransomNote[i]) - ord('a')):
            if a[ord(ransomNote[i]) - ord('a')] > b[ord(ransomNote[i]) - ord('a')]:
                return False
            else:
                pass
        else:
            return False

    return True
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容