CODEWITHSUNDEEP
javascriptarraystime-complexitybig-o
user6248190
user6248190

Reputation: 1271

Reducing time complexity in forEach loop

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?

Upvotes: 1

Views: 701

Answers (1)

Aplet123
Aplet123

Reputation: 35512

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).

Upvotes: 3

Related Questions