c++ - 用字符 A-Z 替换字符串中的每个字母(运行时问题)

Question

我目前正在编写一个拼写检查程序，如果单词拼写错误，它会生成建议。生成建议的算法之一将单词中的每个字母替换为 A-Z 中的每个字母(例如，如果正在拼写检查“phkne”，它会找到单词“phone”)。这是我用来执行此操作的当前函数

//replace each letter in the word with all letters from the alphabet
void replaceLetters(string word, Hashtable & wordList)
{
  char letters[] = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
  string copy = word;
  for (int i = 0; i < word.length() + 1; i++)
    {
      for (int j = 0; j < 25; j++)
        {
          copy = word;
          replace(copy.begin(), copy.end(), copy[i], letters[j]);
          if (wordList.contains(copy))
            {
                  cout << copy << endl; 
            }
        }
    }
}

此解决方案有效，但运行时速度极慢。我假设字母字符和嵌套的 for 循环会减慢速度，但我想不出更快的解决方案。

这是我的哈希表实现中的包含函数

bool Hashtable::contains(string item)
{
  for (int i = 0; i < size; i++)
    {
      for (int j = 0; j < table[i].size() + 1; j++)
        {
          if (table[i].get(j) == item)
            {
               return true;
            }
        }
    }
  return false;
}

Answer 1

速度很大程度上取决于您的Hashtable 的实现，因为它的contains() 方法是在代码的 HitTest 路径中调用的。您发布的 contains() 方法表明您的方法根本不是哈希表，并且由于它执行详尽搜索，因此速度非常慢。

不要重新发明轮子(尤其是使用非常慢的轮子)，一定要使用尽可能快的哈希表(读取速度最快，而不是写入速度最快)。也许是 std:unordered_map 或 std::unordered_set，但请做好研究。

也许您也可以尝试不同的算法，例如使用一些启发式算法来避免搜索可能解决方案的整个空间。一种可能是计算 Levenshtein distance在你的单词和字典中的每个单词之间，保留一个短距离的列表。