LeetCode Notes: Ransom Note

Question

Given two stings `ransomNote` and `magazine`, return `true` if `ransomNote` can be constructed from `magazine` and `false` otherwise.

Each letter in `magazine` can only be used once in `ransomNote`.

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

Constraints:

• `1 <= ransomNote.length, magazine.length <= 105`
• `ransomNote` and `magazine` consist of lowercase English letters.

Solution One

Analysis:

Traverse the string `ransomNote`, check whether each character is in `magazine`, because each character in `magazine` can only be used once in `ransomNote`, after checking, you need to delete the characters matched by `magazine` . Returns false if there is no match.

Code:

``````/**
* @param {string} ransomNote
* @param {string} magazine
* @return {boolean}
*/
var canConstruct = function (ransomNote, magazine) {
// Traverse the string ransomNote
let find = ransomNote.split("").findIndex((n) => {
// Get the position of each ransomNote character in magazine
let i = magazine.indexOf(n);
if (i > -1) {
// If the character exists in the magazine, remove this character to prevent the next repeated match
// If it can always match, then findIndex returns the result find is equal to -1, that is, the final result returns true
magazine = magazine.slice(0, i) + magazine.slice(i + 1, magazine.length);
} else {
// If the character does not exist in the magazine, it does not meet the requirements, findIndex returns the result find is not equal to -1, that is, the final result returns false
return true;
}
});
return find === -1 ? true : false;
};
``````

Solution Two

Analysis:

1. Traverse `magazine` and count the number of occurrences of each letter of `magazine`
2. Traverse `ransomNote`, deduct the same letters that appear in `ransomNote` from the statistical results, and return `false` once it is found that `ransomNote` has more letters than `magazine`

Code:

``````/**
* @param {string} ransomNote
* @param {string} magazine
* @return {boolean}
*/
var canConstruct = function (ransomNote, magazine) {
// Construct an array of length 26 filled with all 0s
const charCount = new Array(26).fill(0);

// Get the char code of the letter a
const aCode = "a".charCodeAt();

// Count the number of occurrences of each letter in the magazine
// For example "acce" statistic result is charCount = [1, 0, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
for (const m of magazine) {
charCount[m.charCodeAt() - aCode]++;
}

// Subtract the letters in ransomNote from the above statistics
for (const r of ransomNote) {
charCount[r.charCodeAt() - aCode]--;

// Once it is found that the number of letters in the magazine is exceeded, it does not meet the requirements
if (charCount[r.charCodeAt() - aCode] < 0) {
return false;
}
}
return true;
};
``````

For problems of the same type of solution, please refer to

LeetCode Notes: Find the Difference