Ransom Note

Loading...LeetCode

Problem

Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters 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

Pseudocode

create a collection of letters and their sum {letters : sum} of magazine with a map
loop over ransomNote and deducut -1 from map for each letter
if !map[letter] or if map[letter] < 0, then there there isn't enough letters for the ransome note 

Solution

var canConstruct = function (ransomNote, magazine) {
  const ransomArr = ransomNote.split("");
  const magazineArr = magazine.split("");
  let ransomObj = {};
  let result = true;

  for (let i = 0; i < magazineArr.length; i++) {
    const letter = magazineArr[i];

    if (!ransomObj[letter]) {
      ransomObj[letter] = 1;
      continue;
    }

    ransomObj[letter] += 1;
  }

  for (let i = 0; i < ransomArr.length; i++) {
    const letter = ransomArr[i];

    if (!ransomObj[letter]) {
      result = false;
      break;
    }

    if (ransomObj[letter] > 0) {
      ransomObj[letter] -= 1;
    }
  }
  return result;
};

Time and Space Complexity

Time

• Two loops are performed, one to create the map, the other to find matching letters for the ransom note. Both are performed independently - O(N)

• Total - O(N)

Space

• Map created to store letters and count, space requirements increases with input size - O(N)

• Total - O(N)