_383.java

package com.fishercoder.solutions;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
/**
 * 383 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
*/
public class _383 {

    public boolean canConstruct_20160924(String ransomNote, String magazine) {
        char[] mchars = magazine.toCharArray();
        int[] mcnt = new int[256];
        for (int i = 0; i < mchars.length; i++) {
            mcnt[mchars[i] - 'a']++;
        }

        char[] rchars = ransomNote.toCharArray();
        for (int i = 0; i < rchars.length; i++) {
            if (mcnt[rchars[i] - 'a'] <= 0) {
                return false;
            }
            mcnt[rchars[i] - 'a']--;
        }
        return true;
    }


    public boolean canConstruct(String ransomNote, String magazine) {
        Map<Character, Integer> ransomMap = new HashMap();
        Set<Character> ransomSet = new HashSet();
        Map<Character, Integer> magazineMap = new HashMap();
        Set<Character> magazineSet = new HashSet();
        char[] ransom = ransomNote.toCharArray();
        char[] maga = magazine.toCharArray();
        for (int i = 0; i < ransom.length; i++) {
            ransomSet.add(ransom[i]);
            ransomMap.put(ransom[i], ransomMap.getOrDefault(ransom[i], 0) + 1);
        }
        for (int i = 0; i < maga.length; i++) {
            magazineSet.add(maga[i]);
            magazineMap.put(maga[i], magazineMap.getOrDefault(maga[i], 0) + 1);
        }

        for (char c : ransomSet) {
            if (!magazineSet.contains(c)) {
                return false;
            }
        }
        for (char c : ransomMap.keySet()) {
            if (!magazineMap.containsKey(c)) {
                return false;
            }
            if (magazineMap.get(c) < ransomMap.get(c)) {
                return false;
            }
        }
        return true;
    }

    public static void main(String... strings) {
        _383 test = new _383();
        String ransomNote = "aa";
        String magazine = "aab";
        System.out.println(test.canConstruct(ransomNote, magazine));
    }
}