Comment on page

# 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

## 代码

### Approach #1 Two HashMaps

class Solution {
// Takes a String, and returns a HashMap with counts of
// each character.
private Map<Character, Integer> makeCountsMap(String s) {
Map<Character, Integer> counts = new HashMap<>();
for (char c: s.toCharArray()) {
int currentCount = counts.getOrDefault(c, 0);
counts.put(c, currentCount + 1);
}
return counts;
}
public boolean canConstruct(String ransomNote, String magazine) {
// Check for obvious fail case.
if (ransomNote.length() > magazine.length()) {
return false;
}
// Make the count maps.
Map<Character, Integer> ransomNoteCounts = makeCountsMap(ransomNote);
Map<Character, Integer> magazineCounts = makeCountsMap(magazine);
// For each unique character, c, in the ransom note:
for (char c : ransomNoteCounts.keySet()) {
// Check that the count of char in the magazine is equal
// or higher than the count in the ransom note.
int countInMagazine = magazineCounts.getOrDefault(c, 0);
int countInRansomNote = ransomNoteCounts.get(c);
if (countInMagazine < countInRansomNote) {
return false;
}
}
// If we got this far, we can successfully build the note.
return true;
}
}

### Approach 3: One HashMap

class Solution {
// Takes a String, and returns a HashMap with counts of
// each character.
private Map<Character, Integer> makeCountsMap(String s) {
Map<Character, Integer> counts = new HashMap<>();
for (char c : s.toCharArray()) {
int currentCount = counts.getOrDefault(c, 0);
counts.put(c, currentCount + 1);
}
return counts;
}
public boolean canConstruct(String ransomNote, String magazine) {
// Check for obvious fail case.
if (ransomNote.length() > magazine.length()) {
return false;
}
// Make a counts map for the magazine.
Map<Character, Integer> magazineCounts = makeCountsMap(magazine);
// For each character in the ransom note:
for (char c : ransomNote.toCharArray()) {
// Get the current count for c in the magazine.
int countInMagazine = magazineCounts.getOrDefault(c, 0);
// If there are none of c left, return false.
if (countInMagazine == 0) {
return false;
}
// Put the updated count for c back into magazineCounts.
magazineCounts.put(c, countInMagazine - 1);
}
// If we got this far, we can successfully build the note.
return true;
}
}