头像

带翅膀的猫

时光荏苒,我们一直都在

《LeetCode刷题(Easy Rank):383. Ransom Note》

 4周前  •   LeetCode  •     •   11  •   0

Question:

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

Solution:

判断ransomNote能否由magazine中的字符组成,如果ransomNote中的某一字符压根就不在magazine中,显然无法组成;如果ransomNote中某一字符的数目大于magazine中该字符的个数,那也是无法组成的。其他情况都可以组成。

JAVAclass Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        Map<Character,Integer> map = new HashMap<>();
        for(int i=0;i<magazine.length();i++){//统计magazine中每个字符的个数
            map.put(magazine.charAt(i),map.getOrDefault(magazine.charAt(i),0)+1);
        }
        for(int i=0;i<ransomNote.length();i++){
            if(map.containsKey(ransomNote.charAt(i))==false||map.get(ransomNote.charAt(i))==0){
                return false;//如果ransomNote中某一字符在magazine中不存在,返回false
            }
            map.put(ransomNote.charAt(i),map.get(ransomNote.charAt(i))-1);//匹配上一个需要更新map中的数目(减一)
        }
        return true;
    }
}

 

上一篇:
下一篇:

 评论


 已有0条评论

    还没有任何评论,你来说两句吧!