Understanding LeetCode 383. Ransom Note
In an effort to continue consistent with my LeetCode practice, I recently made another submission to this problem from the list of “Challenges for New Users”: 383. Ransom Note.
Similarly to the last challenge I posted about in “Understanding LeetCode”, this was not a really time-consuming submission, and, at least for this solution, no deep understanding of algorithms and data structures was needed.
The platform’s problem number 383 will ask the user to , “Given two strings, ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise”. And follows “Each letter in magazine can only be used once in ransomNote”.
The problem has two standard test cases (more can be added if desired):
Example 1:
Input: ransomNote = “a”, magazine: “b”
Output: false
Example 2:
Input: ransomNote = “aa”, magazine: “ab”
Output: false
Example 3:
Input: ransomNote: “aa”, magazine: “aab”
Output: true
There are also two constraints for the problem to be solved:
- 1 ≤ ransomNote.length, magazine.length ≤ 10⁵, or both input’s length have to be between 1 and 10⁵;
- ransomNote and magazine consist of lowercase English characters;
The initial code provided by the platform for the function to be built around is the following:
/**
* @param {string} ransomNote
* @param {string} magazine
* @return {boolean}
*/
var canConstruct = function(ransomNote, magazine) {};
As usual, I’m swapping that structure for an arrow function one and using a constant instead of a variable to hold the function, but this is not a necessary step. The first verification I want to make before applying any logic is to check whether both inputs “ransomNote” and “magazine” exist. I know both of these are also not necessary for the solution since we already have the two constraints mentioned above, but it is not a bad idea to develop the habit to have such checks when we’re writing a function with parameters.
/**
* @param {string} ransomNote
* @param {string} magazine
* @return {boolean}
*/
const canConstruct = (ransomNote, magazine) => {
if (!ransomNote) return true;
if (!magazine) return false;
};
The logic for this one is simple and straightforward: the “ransomNote” string should be iterated using a loop — we’re using a for loop — and for every iteration the program is going to check if the “magazine” string includes the same letter as the one being analyzed from “ransomNote”. We can do that with the help of JavaScript’s native String.prototype.includes() function. If the denied verification passes, meaning the magazine string doesn’t include a given letter from the ransomNote string, the program will return false.
/**
* @param {string} ransomNote
* @param {string} magazine
* @return {boolean}
*/
const canConstruct = (ransomNote, magazine) => {
if (!ransomNote) return true;
if (!magazine) return false;
for (let i = 0; i < ransomNote.length; i++) {
if (!magazine.includes(ransomNote[i])) return false;
}
};
Otherwise, the program should remove said letter from magazine’s string and continue the loop.
/**
* @param {string} ransomNote
* @param {string} magazine
* @return {boolean}
*/
const canConstruct = (ransomNote, magazine) => {
if (!ransomNote) return true;
if (!magazine) return false;
for (let i = 0; i < ransomNote.length; i++) {
if (!magazine.includes(ransomNote[i])) return false;
magazine = magazine.replace(ransomNote[i], "");
}
};
In case the program is able to finish the loop, it means that every letter within the ransomNote string can be found inside the magazine string. For that, we’re returning true:
/**
* @param {string} ransomNote
* @param {string} magazine
* @return {boolean}
*/
const canConstruct = (ransomNote, magazine) => {
if (!ransomNote) return true;
if (!magazine) return false;
for (let i = 0; i < ransomNote.length; i++) {
if (!magazine.includes(ransomNote[i])) return false;
magazine = magazine.replace(ransomNote[i], "");
}
return true
};
It should be reinforced that this is not supposed to be the definitive or standard solution to LeetCode’s problem 383, although it seems to be among the most popular ones for JS the last time I checked.
Did you find any mistakes in the text above? Chances are you did, as I wrote and edited it myself as a non-native English speaker, so feel free to reach out to point them so I can improve it for the next readers. It’ll be greatly appreciated.
Talk soon,