DEV Community

Cover image for ransom note - updated
JP Antunes
JP Antunes

Posted on

1

ransom note - updated

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;
};

Sentry blog image

How I fixed 20 seconds of lag for every user in just 20 minutes.

Our AI agent was running 10-20 seconds slower than it should, impacting both our own developers and our early adopters. See how I used Sentry Profiling to fix it in record time.

Read more

Top comments (0)

nextjs tutorial video

Youtube Tutorial Series 📺

So you built a Next.js app, but you need a clear view of the entire operation flow to be able to identify performance bottlenecks before you launch. But how do you get started? Get the essentials on tracing for Next.js from @nikolovlazar in this video series 👀

Watch the Youtube series

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay