Leetcode 383 Ransom Note
Ransom Note – LeetCode
Ransom Note – Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise.
The idea is pretty simple, we use a map to record the number appearance for each letter from the ransomNote. Then we go to magazine and see if each letter can be used in the ransomNote. Each time we see a letter from magazine in ransomNote, we decrease the count from the map for that letter. Here we will use another variable totalNumberOfLetters to check if all letters can be constructed from magazine.
Solution
/**
* @param {string} ransomNote
* @param {string} magazine
* @return {boolean}
*/
var canConstruct = function(ransomNote, magazine) {
let ransomNoteMap = {};
let totalNumberOfLetters = ransomNote.length;
for(let i = 0; i < ransomNote.length; i++) {
if(!ransomNoteMap[ransomNote[i]]) {
ransomNoteMap[ransomNote[i]] = 1;
} else {
ransomNoteMap[ransomNote[i]]++;
}
}
for(let i = 0; i < magazine.length; i++) {
let letter = magazine[i];
if(ransomNoteMap[letter]) {
ransomNoteMap[letter]--;
totalNumberOfLetters--;
}
}
return totalNumberOfLetters === 0;
};Time Complexity:
O(n) where n is the larger one of the length of magazine and ransomNote
Space Complexity:
O(n) where n is the larger one of the length of magazine and ransomNote