Reducing time complexity in forEach loop

Question

I am building a simple hangman game using Javascript and wanted to know what the best way to optimise my code would be.

const Hangman = function (word, remainingGuesses) {
  this.word = word.toLowerCase().split("");
  this.remainingGuesses = remainingGuesses;
  this.guessedLetters = [];
};

Hangman.prototype.getPuzzle = function () {
  let puzzle = "";
  this.word.forEach((char) => {
    this.guessedLetters.includes(char) || char === " "
      ? (puzzle += char)
      : (puzzle += "*");
  });
  return puzzle;
};

At the moment as you can see from the above code, I am doing a forEach loop for this.word and then inside the forEach loop I am using .includes() to find whether a word has been guessed, if not then set the char to *.

At the moment I believe the time complexity of O(n2) due to the includes() inside the forEach what would be a better way to rewrite the getPuzzle() function?

Aplet123 · Accepted Answer · 2020-12-28 14:24:33Z

3

Use a Set for guessedLetters for constant time lookup:

const Hangman = function (word, remainingGuesses) {
  this.word = word.toLowerCase().split("");
  this.remainingGuesses = remainingGuesses;
  this.guessedLetters = new Set(); // this is a Set now
};

Hangman.prototype.getPuzzle = function () {
  let puzzle = "";
  this.word.forEach((char) => {
    // use Set.has instead of Array.includes
    this.guessedLetters.has(char) || char === " "
      ? (puzzle += char)
      : (puzzle += "*");
  });
  return puzzle;
};

You can add a new guessed letter with this.guessedLetters.add(char).

answered Dec 28, 2020 at 14:24

Aplet123

35.8k1 gold badge41 silver badges66 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

WesleyAC Over a year ago

Yes, using a Set or hash is the right way to go for faster lookups (as opposed to repeated linear searches through an array). BUT, since strings are immutable, your forEach loop is STILL doing a lot of unnecessary work; every use of '+=' has to recreate the entire string over again. To avoid this, change the puzzle variable to an array, change "(puzzle += char)" to "puzzle.push(char)" (same for "*"), and return puzzle.join(''). This means that you build the string only once.

Daniel Grabowski Over a year ago

Very interesting and clean solution with the Set. I have one question though, isn't a simple object (map of key and value) even faster? The object would be something like this: { 'a': 'a', 'b': 'b' }, where 'a' and 'b' are the guessed letters.

Aplet123 Over a year ago

Sets are generally faster than objects.

Daniel Grabowski Over a year ago

I got curious about this comparison because I always thought objects were faster. So I found a benchmark that says that objects are much faster than Sets and Maps. Sadly I couldn't find which operations were used to get those results. measurethat.net/Benchmarks/Show/5364/0/set-vs-object-vs-map

Collectives™ on Stack Overflow

Reducing time complexity in forEach loop

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related