loading...
Cover image for ransom note - updated

ransom note - updated

jpantunes profile image JP Antunes ・2 min read

Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false. Each letter in the magazine string can only be used once in your ransom note.

Update: It was troubling me that I couldn't get a higher result, and since JS gives us many ways of doing the same thing I decided to try one more time.

Now with a 90th percentile + result, I'm much happier :-)

// Runtime: 64 ms, faster than 94.72% of JavaScript online submissions for Ransom Note.
// Memory Usage: 38.4 MB, less than 33.33% of JavaScript online submissions for Ransom Note.

var canConstruct = function(ransomNote, magazine) {
  if (ransomNote.length > magazine.length) return false;
  let charMap = [];
  for (let i = 0; i < ransomNote.length; i++) {
      if (magazine.indexOf(ransomNote[i]) == -1) return false;
      let char = ransomNote.codePointAt(i);
      charMap[char] = charMap[char] - 1 || -1;
  }

  for (let i = 0; i < magazine.length; i++) {
      let char = magazine.codePointAt(i);
      charMap[char] = charMap[char] + 1 || 1;
  }
  for (const charCount of charMap) if (charCount < 0) return false;
  return true; 
};

** previously **
Didn't get a particularly impressive result, but here's 3 valid solutions exploring different data structures and approaches.

// Runtime: 76 ms, faster than 77.31% of JavaScript online submissions for Ransom Note.
// Memory Usage: 38.1 MB, less than 33.33% of JavaScript online submissions for Ransom Note

var canConstruct = function(ransomNote, magazine) {
    let retVal = true;
    const noteCharMap = [...ransomNote].reduce((acc, val, _, arr) => {
        acc[val] = acc[val] + 1 || 1;
        if (magazine.indexOf(val) == -1) {
            retVal = false;
            arr.pop(); //force early return with arr mutation
        }
        return acc;
    }, {});
    if (!retVal) return false;

    const magzCharMap = [...magazine].reduce((acc, val) => {
        acc[val] = acc[val] + 1 || 1;
        return acc;
    }, {});
    for (const [char, count] of Object.entries(noteCharMap)) {
        if (magzCharMap[char] < count) return false;
    }
    return true;
};
var canConstruct = function(ransomNote, magazine) {
    let charMap = {};
    for (const char of ransomNote) {
        if (magazine.indexOf(char) == -1) return false;
        charMap[char] = charMap[char] + 1 || 1;
    }
    for (const char of magazine) {
        if (charMap[char]) charMap[char] -= 1;
        if (charMap[char] == 0) delete charMap[char];
    }
    for (const _ in charMap) return false;
    return true;
};
var canConstruct = function(ransomNote, magazine) {
    const charMap = new Map();
    for (const char of ransomNote) {
        if (magazine.indexOf(char) == -1) return false;
        charMap.set(char, charMap.get(char) + 1 || 1)
    }
    for (const char of magazine) {
        charMap.set(char, charMap.get(char) - 1 || 0)
        if (charMap.get(char) <= 0) charMap.delete(char);
    }
    for (const _ of charMap) return false;
    return true;
};

Posted on Apr 19 by:

Discussion

markdown guide