Ransom Note
Easy
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
int[26]
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int[] alphabet = new int[26];
for (int i = 0; i < magazine.length(); i++) {
alphabet[magazine.charAt(i) - 'a'] += 1;
}
for (int j = 0; j < ransomNote.length(); j++) {
alphabet[ransomNote.charAt(j) - 'a'] -= 1;
if (alphabet[ransomNote.charAt(j) - 'a'] < 0) {
return false;
}
}
return true;
}
}
HashMap
public boolean canConstruct(String ransomNote, String magazine) {
Map<Character, Integer> map = new HashMap<>();
for (char c : magazine.toCharArray()) {
int count = map.containsKey(c) ? map.get(c) + 1 : 1;
map.put(c, count);
}
for (char c : ransomNote.toCharArray()) {
int newCount = map.containsKey(c) ? map.get(c) - 1 : -1;
if (newCount == -1) return false;
map.put(c, newCount);
}
return true;
}
Last updated
Was this helpful?