美文网首页
leetcode-383 Ransom Note

leetcode-383 Ransom Note

作者: Fluxay | 来源:发表于2016-08-16 11:29 被阅读119次

题目描述:

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

相关文章

网友评论

      本文标题:leetcode-383 Ransom Note

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