这是一个谷歌面试题，我发现大多数在线答案使用HashMap或类似的数据结构。如果可能的话，我想尝试使用Trie来解决问题。有人可以给我一些提示吗？
以下是问题描述： 给定一个字典，格式为每行包含一个单词的文件。例如，
abacus
deltoid
gaff
giraffe
microphone
reef
qar
你还会得到一组字母，例如：
{a, e, f, f, g, i, r, q}.
任务是在字典中找到能够用给定字母集合拼出的最长单词。例如，对于上述示例值，正确答案是“giraffe”。（请注意，“reef”不是可能的答案，因为字母集合仅包含一个“e”）。
首选Java实现。
没有Java代码，你可以自己想出。
假设我们需要多次执行此操作，以下是我会做的：
首先为字典中每个单词创建“签名”，由26位组成，其中bit[letter]设置为当且仅当该单词包含一个或多个letter。这些签名可以编码为Java int。
然后创建一个映射，将签名映射到具有该签名的单词列表。
使用预计算映射进行搜索：
创建要查找单词的字母集的签名。
然后迭代映射的键，寻找其中(key & (~signature) == 0)的键。这给出了一个短列表，“可能性”不包含任何不在所需字母集中的字母。
在短列表中遍历，寻找具有每个所需字母的正确数量的单词，并记录最长的匹配项。
注：
虽然主要搜索大致上是对字典中单词数的O(N)级别，但测试非常便宜。
这种方法的优点是需要一个相对较小的内存数据结构，并且（很可能）具有良好的局部性。这很有助于更快的搜索。
以下是加速上述O(N)搜索步骤的想法。
(key & (~signature) == 0)？你确定你不是想用(key & signature != 0)吗？考虑这样一种情况，你的整个字典只有一个单词00000000000000000000000000001111，它代表着"ABCD"，而你的搜索签名是['A','B']或者00000000000000000000000000000011。在这种情况下，你永远无法满足条件(key & (~signature) == 0)，因此也永远无法找到答案，而事实上显然的答案就是"ABCD"（你的字典中唯一的单词）。 - The111public class LongestWord {
class TrieNode {
char value;
List<TrieNode> children = new ArrayList<>();
String word;
public TrieNode() {
}
public TrieNode(char val) {
this.value = val;
}
public void add(char[] array) {
add(array, 0);
}
public void add(char[] array, int offset) {
for (TrieNode child : children) {
if (child.value == array[offset]) {
child.add(array, offset + 1);
return;
}
}
TrieNode trieNode = new TrieNode(array[offset]);
children.add(trieNode);
if (offset < array.length - 1) {
trieNode.add(array, offset + 1);
} else {
trieNode.word = new String(array);
}
}
}
private TrieNode root = new TrieNode();
public LongestWord() {
List<String> asList = Arrays.asList("abacus", "deltoid", "gaff", "giraffe",
"microphone", "reef", "qar");
for (String word : asList) {
root.add(word.toCharArray());
}
}
public String search(char[] cs) {
return visit(root, cs);
}
public String visit(TrieNode n, char[] allowedCharacters) {
String bestMatch = null;
if (n.children.isEmpty()) {
// base case, leaf of the trie, use as a candidate
bestMatch = n.word;
}
for (TrieNode child : n.children) {
if (contains(allowedCharacters, child.value)) {
// remove this child's value and descent into the trie
String result = visit(child, remove(allowedCharacters, child.value));
// if the result wasn't null, check length and set
if (bestMatch == null || result != null
&& bestMatch.length() < result.length()) {
bestMatch = result;
}
}
}
// always return the best known match thus far
return bestMatch;
}
private char[] remove(char[] allowedCharacters, char value) {
char[] newDict = new char[allowedCharacters.length - 1];
int index = 0;
for (char x : allowedCharacters) {
if (x != value) {
newDict[index++] = x;
} else {
// we removed the first hit, now copy the rest
break;
}
}
System.arraycopy(allowedCharacters, index + 1, newDict, index,
allowedCharacters.length - (index + 1));
return newDict;
}
private boolean contains(char[] allowedCharacters, char value) {
for (char x : allowedCharacters) {
if (value == x) {
return true;
}
}
return false;
}
public static void main(String[] args) {
LongestWord lw = new LongestWord();
String longestWord = lw.search(new char[] { 'a', 'e', 'f', 'f', 'g', 'i',
'r', 'q' });
// yields giraffe
System.out.println(longestWord);
}
}
我建议阅读这本书《Cracking the Coding Interview: 150 Programming Questions and Solutions》，它会引导你决策和构建那些专门用于面试问题的算法。
Arrays.asList("abacus", "deltoid", "gaff", "gira", "giraffe", "microphone", "reef", "qar"); 和 lw.search(new char[] { 'a', 'g', 'i', 'r', 'q' });，应该返回 gira 而不是 qar。 - CSnerdTrieNode visitNode( TrieNode n, LetterCollection c )
{
TreeNode deepestNode = n;
for each Letter l in c:
TrieNode childNode = n.getChildFor( l );
if childNode:
TreeNode deepestSubNode = visitNode( childNode, c.without( l ) );
if deepestSubNode.stringLength > deepestNode.stringLength:
deepestNode = deepestSubNode;
return deepestNode;
}
hash(A), hash(B), hash(C), hash(D) // 1-combinations
hash(AB), hash(AC), hash(AD), hash(BC), hash(BD), hash(CD) // 2-combinations
hash(ABC), hash(ABD), hash(ACD), hash(BCD) // 3-combinations
hash(ABCD) // 4-combinations
如果按照这个顺序搜索哈希值，你找到的最后一个匹配项将是最长的。
这最终会导致运行时间取决于搜索集的长度而不是字典的长度。如果M是搜索集中字符的数量，则哈希查找的数量是总和M choose 1 + M choose 2 + M choose 3 + ... + M choose M，这也是搜索集的幂集的大小，因此它是O(2^M)。乍一看，这听起来真的很糟糕，因为它是指数级的，但是为了让事情更清楚，如果您的搜索集大小为10，则只会有大约1000次查找，这可能比实际现实场景中的字典大小要小得多。当M = 15时，我们获得32000个查找，而实际上，有多少英语单词的长度超过15个字符呢？
然而，我可以想到两种（备选）优化方法：
1）首先搜索更长的匹配项，例如M组合，然后是（M-1）组合等。一旦找到匹配项，您就可以停止！很可能您只覆盖了搜索空间的一小部分，最坏的情况可能只有一半。
2) 首先搜索较短的匹配项（1个组合，2个组合等）。假设在第2级出现了一个错误（例如，字典中没有仅由A和B组成的字符串）。使用一个辅助数据结构（比如位图），可以检查字典中的任何单词是否部分地由A和B组成（与主哈希表相反，主哈希表检查的是完全的组合）。如果在辅助位图上也出现了错误，那么就知道可以跳过包含A和B的所有更高级别的组合（即可以跳过hash(ABC)、hash(ABD)和hash(ABCD)，因为没有单词同时包含A和B）。这利用了Apriori原则，并且随着M的增长和错误变得更频繁，可以大大减少搜索空间。编辑：我意识到我所抽象掉的与“辅助数据结构”相关的细节是重要的。当我对这个想法思考得更多时，我意识到它倾向于作为一个子过程进行完整的字典扫描，这违背了整个方法的初衷。不过，似乎还应该有一种方法在这里使用Apriori原则。我认为以上的答案都忽略了关键点。我们有一个27维的空间，第一维是长度，其余的是每个字母的坐标。在这个空间中，我们有点，这些点就是单词。一个单词的第一个坐标是它的长度。其他坐标是每个字母出现的次数。例如单词abacus, deltoid, gaff, giraffe, microphone, reef, qar, abcdefghijklmnopqrstuvwxyz的坐标如下：
[3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[6, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0]
[7, 0, 0, 0, 2, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]
[4, 1, 0, 0, 0, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[7, 1, 0, 0, 0, 1, 2, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[10, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 2, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[4, 0, 0, 0, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[3, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[26, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
一个带有坐标的集合的良好结构是R树或R*-树。给定你的集合[x0, x1, ..., x26]，你需要查询包含最多xi个字母的所有单词，对于每个字母。你的搜索时间复杂度为O(log N)，其中N是字典中单词的数量。然而，你不想查看与查询匹配的所有单词中最长的单词。这就是为什么第一维很重要。
你知道最长单词的长度在0到X之间，其中X=sum(x_i, i=1..26)。你可以从X到1进行迭代搜索，但也可以使用二分查找算法来查询长度。你将数组的第一维用作查询。你从a=X开始到b=X/2。如果至少有一个匹配项，你就从a到(a+b)/2进行搜索，否则你就从b到b-(a-b)/2=(3b-a)/2进行搜索。你重复这个过程直到b-a=1。现在你已经得到了最大长度和所有与该长度匹配的结果。
这个算法的时间复杂度比上面的算法要高效得多。时间复杂度为O(ln(N)×ln(X))。具体实现取决于你使用的R-tree库。
Groovy（几乎就是Java）：
def letters = ['a', 'e', 'f', 'f', 'g', 'i', 'r', 'q']
def dictionary = ['abacus', 'deltoid', 'gaff', 'giraffe', 'microphone', 'reef', 'qar']
println dictionary
.findAll{ it.toList().intersect(letters).size() == it.size() }
.sort{ -it.size() }.head()
选择用什么类型的集合来保存字典对算法来说并不重要。如果你需要实现一个 trie，那就另当别论了。否则，只需从适当的库中创建一个来保存数据即可。据我所知，Java 和 Groovy 的标准库中都没有这样的库。
我尝试用C++编写这个问题的代码，其中我创建了自己的哈希键，并使用给定字符的所有组合。
从最大长度到1遍历这些输入字符的所有组合
这是我的解决方案
#include "iostream"
#include <string>
using namespace std;
int hash_f(string s){
int key=0;
for(unsigned int i=0;i<s.size();i++){
key += s[i];
}
return key;
}
class collection{
int key[100];
string str[10000];
public:
collection(){
str[hash_f( "abacus")] = "abacus";
str[hash_f( "deltoid")] = "deltoid";
str[hash_f( "gaff")] = "gaff";
str[hash_f( "giraffe")] = "giraffe";
str[hash_f( "microphone")] = "microphone";
str[hash_f( "reef")] = "reef";
str[hash_f( "qar")] = "qar";
}
string find(int _key){
return str[_key];
}
};
string sub_str(string s,int* indexes,int n ){
char c[20];
int i=0;
for(;i<n;i++){
c[i] = s[indexes[i]];
}
c[i] = 0;
return string(c);
}
string* combination_m_n(string str , int m,int n , int& num){
string* result = new string[100];
int index = 0;
int * indexes = (int*)malloc(sizeof(int)*n);
for(int i=0;i<n;i++){
indexes[i] = i;
}
while(1){
result[index++] = sub_str(str , indexes,n);
bool reset = true;
for(int i=n-1;i>0;i--)
{
if( ((i==n-1)&&indexes[i]<m-1) || (indexes[i]<indexes[i+1]-1))
{
indexes[i]++;
for(int j=i+1;j<n;j++)
indexes[j] = indexes[j-1] + 1;
reset = false;
break;
}
}
if(reset){
indexes[0]++;
if(indexes[0] + n > m)
break;
for(int i=1;i<n;i++)
indexes[i] = indexes[0]+i;
}
}
num = index;
return result;
}
int main(int argc, char* argv[])
{
string str = "aeffgirq";
string* r;
int num;
collection c;
for(int i=8;i>0;i--){
r = combination_m_n(str, str.size(),i ,num);
for(int i=0;i<num;i++){
int key = hash_f(r[i]);
string temp = c.find(key);
if( temp != "" ){
cout << temp ;
}
}
}
}
首先要注意的是，您可以完全忽略字母顺序。
有一个类似于 trie 的结构如下：
按照以下方式构建 trie：
对于每个单词，对其字母进行排序，并将排序后的字母插入到 trie 中（通过从根创建这些字母的路径），在此过程中创建所有所需的节点。并将单词存储在最终节点处。
如何进行查找：
对于给定的一组字母，查找所有字母的子集（其中大多数希望不存在），并输出遇到的每个节点的单词。
复杂度：
O(k!)，其中k是提供的字母数量。哎呀！但幸运的是，在trie中单词越少，路径就越少，这将花费更少的时间。而k是提供的字母数量（应该相对较小），而不是trie中单词的数量。
实际上，它可能更接近于O(min(k!,n))，看起来好多了。请注意，如果您提供了足够的字母，您将不得不查找所有单词，因此在最坏情况下，您必须进行O(n)的工作，因此在最坏情况下的复杂度方面，您无法做得更好。
示例：
输入：
aba
b
ad
da
la
ma
已排序：
aab
b
ad
ad
al
am
字典树：（仅显示非空子节点）
root
/ \
a b
/-/|\-\
a b d l m
|
b
adb的查找：
a
b
d
ad和dab
ba子节点，因为只有 >= b 的子节点存在d子节点，返回d子节点，停止假设有一个大型字典和一个不到10或11个成员的字母集（例如给定的示例），最快的方法是构建一个包含可能由这些字母组成的单词的树，然后将单词列表与该树进行匹配。换句话说，您的字母树的根节点有七个子节点：{a，e，f，g，i，r，q}。 "a" 的分支有六个子节点 {e，f，g，i，r，q}，等等。因此，该树包含了可以用这些字母组成的每个可能的单词。
遍历列表中的每个单词并将其与树进行匹配。如果匹配的长度最大（使用所有字母），则完成。如果单词长度小于最大值，但比以前匹配的任何单词都长，请记住它，这是“到目前为止最长的单词”（LWSF）。忽略长度小于或等于 LWSF 的任何单词。同时，忽略长度超过字母列表长度的任何单词。
一旦构建了字母树，这就是一个线性时间算法，因此只要单词列表显着大于字母树，它就是最快的方法。