Can phrase be made from whole words in another string?

Question

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?

Answer 1

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