时间戳

首页 > 解决方案 > 降低 forEach 循环中的时间复杂度

javascript - 降低 forEach 循环中的时间复杂度

问题描述

我正在使用 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;
};

目前，从上面的代码中可以看出，我正在执行一个forEach循环 forthis.word然后在forEach我.includes()用来查找是否已猜到单词的循环内，如果没有，则将 char 设置为*.

目前我相信O(n2)由于includes()内部的时间复杂度，重写函数forEach的更好方法是什么？getPuzzle()

标签： javascriptarraystime-complexitybig-o

解决方案

使用SetforguessedLetters进行恒定时间查找：

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

推荐阅读