LeetCode Notes: Ransom Note

#leetcode

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

Reference

Comments