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

ps: Ransom Note 勒索信，就是用报纸、杂志出版物，裁剪其中的单词或句子，粘贴组成勒索信的文本，防止自己的笔迹被识别。

Solution:

这道题与 389. Find the Difference 类似，都是查找一个数组，看里面是否包含另一个数组中的元素（考虑重复）。思路是统计magazine中有哪些字母，每个字母都有多少个，从而是否足够ransom note使用。

public class Solution 
{
    public boolean canConstruct(String ransomNote, String magazine) 
    {
        //under this circumstance we cannot make a ransom note from an empty magazine, so false
        if(magazine.length() == 0 && ransomNote.length() > 0)
            return false;

        int[] dict = new int[26];   // Both strings contain only lowercase letters
        for(int i = 0; i < magazine.length(); i++)
        {
            dict[(int)magazine.charAt(i) - 'a']++;
        }
        for(int j = 0; j < ransomNote.length(); j++)
        {
            if(--dict[(int)ransomNote.charAt(j) - 'a'] < 0)
                return false;
        }
        return true;
    }
}

也可以考虑使用HashTable，因为HashTable提供的 <Key, Value> pair 适用于统计字母（key）和该字母出现的次数（value）。

Solution：

public class Solution 
{
    public boolean canConstruct(String ransomNote, String magazine) 
    {
        char[] ransomNoteArray = ransomNote.toCharArray();
        char[] magazineArray = magazine.toCharArray();
        Map<Character, Integer> dict = new HashMap<>();
        for(char i : magazineArray)
        {
            int newCount = dict.getOrDefault(i, 0) + 1; // update count of current char i
            dict.put(i, newCount);
        }
        for(char i : ransomNoteArray)
        {
            int newCount = dict.getOrDefault(i, 0) - 1;
            if(newCount < 0)
                return false;
            dict.put(i, newCount);
        }
        return true;
    }
}

发现Map，Table， Set这几个API掌握的不好，需要总结一下。