[LeetCode]Ransom Note

题目描述:

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

题目大意:

给定两个字符串ransomNote和magazine,编写函数判断magazine中的字符是否可以完全包含ransomNote中的字符。

注意:可以假设字符串中只包含小写字母。

解题思路:

利用Python的collections.Counter类统计字符个数,然后做差即可。

Python代码:

class Solution(object):
    def canConstruct(self, ransomNote, magazine):
        """
        :type ransomNote: str
        :type magazine: str
        :rtype: bool
        """
        ransomCnt = collections.Counter(ransomNote)
        magazineCnt = collections.Counter(magazine)
        return not ransomCnt - magazineCnt

使用Java解题时可以用数组统计字母的个数。

Java代码:

public class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] cnt = new int[26];
        for (int i = 0; i < magazine.length(); i++) {
            cnt[magazine.charAt(i) - 'a']++;
        }
        for (int i = 0; i < ransomNote.length(); i++) {
            if(--cnt[ransomNote.charAt(i)-'a'] < 0) {
                return false;
            }
        }
        return true;
    }
}

 

本文链接:http://bookshadow.com/weblog/2016/08/11/leetcode-ransom-note/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码