3
\$\begingroup\$

I am working to solve this HackerRank puzzle: Hash Tables: Ransom Note

The premise is that if I am given a string like this:

give one grand today

I can find a match for each of the words in the following string, but I cannot use the same word more than once:

give me one grand today night

My code looks like this:

  var ransom = "give one grand today".split(' ');
  var magazine = "give me one grand today night".split(' ');
  var result = ransom.reduce(function(words, word) {
    var index = magazine.indexOf(word);

    if(index !== -1) {
      words.push(word);
      magazine.splice(index, 1);
    }

    return words;
  }, []);

  console.log(result.length === ransom.length ? 'Yes' : 'No' );

My code works for most of the test cases but times out for the large inputs.

How can I make my code faster?

\$\endgroup\$
  • \$\begingroup\$ It would help if you could provide a case where it doesn't work. (Though I would do this wih hash tables like Flambino), \$\endgroup\$ – Marc Rohloff Mar 24 '17 at 16:34
  • \$\begingroup\$ You might be interested by my JavaScript solution to the challenge! \$\endgroup\$ – Phrancis Mar 24 '17 at 18:22
4
\$\begingroup\$

Well, the challenge is named "Hash Tables: ..." so that might be a clue to use JS objects (which are basically hashes) instead of arrays. The array-searching (indexOf) is rather slow.

So it might work to instead treat the dictionary/vocabulary (the magazine words) as keys/property names.

function check(ransomString, magazineString) {
  const vocabulary = magazineString
    .split(" ")
    .reduce((hash, word) => {
      hash[word] = (hash[word] || 0) + 1;
      return hash;
    }, {});

  return ransomString
    .split(" ")
    .every(word => {
      vocabulary[word] -= 1;
      return vocabulary[word] >= 0;
    });
}

Here, the vocabulary object is built with the magazine words as keys, and a numeric count as its value, in case a word occurs more than once in the magazine. Keys in JS objects are automatically strings and case-sensitive.

To match it against the ransom note, we decrement the count for each of the words in the note, as we match them. If the word isn't in the vocabulary at all vocabulary[word] -= 1 will result in NaN, and NaN >= 0 is false.

Note: I don't actually see in the challenge description that words can only be used once, although it makes a lot of sense for the "story" they're telling (although the kidnapper could have bought multiple magazines). If the once-only constraint isn't there, you can do:

function check(ransomString, magazineString) {
  const vocabulary = magazineString
    .split(" ")
    .reduce((hash, word) => {
      hash[word] = true;
      return hash;
    }, {});

  return ransomString
    .split(" ")
    .every(word => vocabulary[word] === true);
}

Alternatively, if the words in magazine are unique already, but can only be used once, you could also do although the above are probably as fast/faster:

function check(ransomString, magazineString) {
  const vocabulary = magazineString
    .split(" ")
    .reduce((hash, word) => {
      hash[word] = true;
      return hash;
    }, {});

  return ransomString
    .split(" ")
    .every(word => {
      if(vocabulary[word] !== true) {
        return false;
      }
      delete vocabulary[word];
      return true;
    });
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.