降低 forEach 循环的时间复杂度

Question

我正在使用 Javascript 构建一个简单的刽子手游戏，想知道优化我的代码的最佳方法是什么。

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

目前你可以从上面的代码中看到，我正在为 this.word 做一个 forEach 循环，然后在 forEach 循环中我使用 .includes() 判断一个词是否被猜中，如果没有则设置字符为 *.

目前我认为 O(n2) 的时间复杂度是由于 forEach 中的 includes() 重写 getPuzzle() 函数的更好方法是什么？

Answer 1

对 guessedLetters 使用 Set 进行恒定时间查找：

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

您可以使用 this.guessedLetters.add(char) 添加一个新的猜中字母。

降低 forEach 循环的时间复杂度

Reducing time complexity in forEach loop

javascript

arrays

big-o

time-complexity