8

这是一道面试题：

给定一个字符串，找出它的所有排列是字典中的一个单词。

我的解决方案：

将字典中的所有单词放入后缀树中，然后在树中搜索字符串的每个排列。

搜索时间是O(n)，其中n是字符串的大小。但是字符串可能有n!排列。

如何提高效率？

4

6 回答 6

9

你的一般方法还不错。

但是，您可以通过重新排列单词以使其所有字符按字母顺序排列，然后在字典中搜索，其中每个单词类似地重新排列为字母顺序并映射到原始单词，您可以避免搜索每个排列。

我意识到这可能有点难以理解，所以这里有一个例子。说你的话是飞跃。将其重新排列为aelp。

现在，在您的字典中，您可能会看到恳求和苍白这两个词。按照建议完成后，您的字典将（除其他外）包含以下映射：

...
aelp -> pale
aelp -> plea
...

所以现在，要找到你的字谜，你只需要找到aelp的条目（例如，使用建议的后缀树方法），而不是全部 4 个！= 24 种跳跃的排列。

于 2011-12-08T04:46:12.880 回答
2

一个快速的替代解决方案 - 完全取决于相关数据结构的大小。

如果字典相当小并且字符串相当长，您可以检查字典中的每个条目并确定它们是否是字符串的排列。你可以更聪明——你可以对字典进行排序并跳过某些条目。

于 2011-12-08T04:38:36.707 回答
1

为什么不使用哈希映射来存储字典单词？所以你得到 O(1) 的查找时间。如果你的输入是英文，你可以建立另一个表来告诉你字典中所有可能的字母，使用这个表，你可以在开头过滤一些输入。下面是一个例子：

result_list = empty;   

for(char in input)
{
   if(char not in letter_table)
   {
      return result_list;
   }
}

for(entry in permutations of input)
{
    if(entry in dictionary_hash_table)
    { 
        result_list->add_entry();
    }
}

return result_list
于 2011-12-08T05:07:18.617 回答
1

你应该把这些词放在一个尝试中。然后，您可以在生成排列时查找该单词。您可以跳过整个排列块，而第一部分不在 trie 中。

http://en.wikipedia.org/wiki/Trie

于 2011-12-08T17:37:32.457 回答
1

您可以构建从排序的字符列表到单词列表的映射。

例如，给定这些：

Array (him, hip, his, hit, hob, hoc, hod, hoe, hog, hon, hop, hos, hot)

你会在内部对它们进行排序：

 Array (him, hip, his, hit, bho, cho, dho, eho, gho, hno, hop, hos, hot)

排序结果：

 Array (bho, cho, dho, eho, gho, him, hip, his, hit, hno, hop, hos, hot)

在这个小样本中，我们没有匹配项，但是对于特定的单词，您可以在内部对其进行排序，并以此为关键字查看您的地图。

于 2011-12-08T04:49:21.360 回答
0

另一个简单的解决方案可能是下面的算法，

1) 使用“next_permutation”找到唯一的排列。

2) 使用“find/find_if”在字典中查找。

于 2011-12-08T06:48:27.327 回答