这是一个谷歌面试问题，我使用 HashMap 或类似的数据结构在网上找到了大多数答案。如果可能，我正在尝试使用 Trie 找到解决方案。任何人都可以给我一些提示吗？
问题是：给你一本字典，文件形式为每行一个单词。例如，
abacus
deltoid
gaff
giraffe
microphone
reef
qar
您还会收到一组信件。例如，
{a, e, f, f, g, i, r, q}.
任务是在字典中找到可以用字母集合拼写的最长单词。例如，上述示例值的正确答案是“长颈鹿”。（请注意，“reef”不是一个可能的答案，因为这组字母只包含一个“e”。）
Java 实现将是首选。
没有Java代码。你可以自己弄清楚。
假设我们需要做很多次，这就是我要做的：
我首先为字典中由 26 位组成的每个单词创建“签名”，如果单词包含一个（或多个）字母实例，则设置 bit[letter]。这些签名可以编码为 Java int。
然后创建一个映射，将签名映射到具有该签名的单词列表。
要使用预先计算的地图进行搜索：
为您要为其查找单词的一组字母创建签名。
然后遍历映射的键以查找键 where (key & (~signature) == 0)。这为您提供了一个简短的“可能”列表，其中不包含任何不在所需字母集中的字母。
遍历短列表，寻找每个所需字母数量正确的单词，记录最长的命中。
笔记：
虽然主要搜索大致O(N)是字典中的单词数量，但测试非常便宜。
这种方法的优点是需要相对较小的内存数据结构，（很可能）具有良好的局部性。这可能有利于更快的搜索。
这是加快上述O(N)搜索步骤的一个想法。
从上面的签名图开始，为所有包含特定对字母的单词创建（预计算）派生图；即一个用于包含 AB 的单词，用于 AC、BC、... 和用于 YZ。然后，如果您正在寻找包含（例如）P 和 Q 的单词，您只需扫描 PQ 导数图即可。这将O(N)大致减少26^2......以额外地图的更多内存为代价。
这可以扩展到 3 个或更多字母，但缺点是内存使用量激增。
另一个潜在的调整是（以某种方式）将初始字母对的选择偏向于不经常出现的字母/对。但这会增加前期开销，这可能大于您从搜索较短列表中获得的（平均）节省。
首先，好问题。面试官想看看你是如何解决这个问题的。在这些类型的问题中，您需要分析问题并仔细选择数据结构。
在这种情况下，我想到了两个数据结构：HashMaps和Tries.
HashMaps不太合适，因为您没有要查找的完整键（您可以使用基于映射的倒排索引，但您说您已经找到了这些解决方案）。你只有零件——那是Trie最合适的地方。
所以尝试的想法是，您可以在遍历树时忽略不在字典中的字符分支。
在您的情况下，树看起来像这样（我省略了非分支路径的分支）：
*
一个
算盘
d
三角肌
G
一个
加夫
一世
长颈鹿
米
麦克风
r
礁
q
卡尔
所以在这个 trie 的每一层，我们查看当前节点的子节点并检查子节点的字符是否在我们的字典中。
如果是：我们深入那棵树并从字典中删除孩子的角色
这一直持续到你碰到一片叶子（不再有孩子），在这里你知道这个词包含这本字典中的所有字符。这是一个可能的候选人。现在我们想回到树中，直到找到另一个可以比较的匹配。如果最新找到的匹配较小，则丢弃它，如果更长，这是我们现在可能的最佳匹配候选。
总有一天，recusion 会结束，你会得到想要的输出。
请注意，如果有一个最长的单词，则此方法有效，否则您将不得不返回候选人列表（这是面试的未知部分，您需要询问面试官希望看到什么作为解决方案）。
所以你需要 Java 代码，这里有一个简单Trie且最长的单词版本：
public 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 》一书，它会指导您完成决策和构建那些专门针对面试问题的算法。
我怀疑基于 Trie 的实现不会非常节省空间，但它会很好地并行化，因为您可以并行下降到树的所有分支并收集您可以从每个顶部分支到达的最深节点给定一组字母。最后，您只需收集所有最深的节点并选择最长的节点。
我将从这个算法开始（对不起，只是伪代码），它不会尝试并行化，而只是使用普通的旧递归（和回溯）来找到最长的匹配：
TrieNode 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;
}
即这个函数应该从trie 的根节点开始，包含整个给定的字母集合。对于集合中的每个字母，您尝试找到一个子节点。如果有，则递归并从集合中删除该字母。在某一时刻，您的信件集合将是空的（最好的情况是，所有信件都被消耗 - 实际上您可以立即退出而不继续遍历特里树），或者将不再有任何剩余信件的孩子 - 在这种情况下，您删除节点本身，因为那是您的“最长匹配”。
如果您更改递归步骤以便并行访问所有子项，收集结果 - 并选择最长的结果并返回它，这可以很好地并行化。
我认为上述答案错过了关键点。我们有一个有 27 个维度的空间，第一个是长度，其他是每个字母的坐标。在那个空间里，我们有点，也就是词。一个词的第一个坐标是他的长度。对于每个字母维度，其他坐标是该字母在该单词中出现的次数。例如算盘、三角体、gaff、giraffe、麦克风、礁、 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-tree或R*-Tree。给定您的集合 [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-(ab)/2=(3b-a)/2。你这样做，直到你有 ba=1。您现在拥有最大的长度以及所有具有此长度的匹配项。
该算法在渐近上比上述算法高效得多。时间复杂度为 O(ln(N)×ln(X))。实现取决于您使用的 R-tree 库。
免责声明：这不是一个特里解决方案，但我仍然认为这是一个值得探索的想法。
创建某种散列函数，只考虑单词中的字母而不考虑它们的顺序（除了排列的情况外，不应发生冲突）。例如，ABCD两者DCBA都生成相同的哈希（但ABCDD不会）。生成这样一个包含字典中每个单词的哈希表，使用链接来链接冲突（另一方面，除非您严格要求找到“所有”最长的单词而不仅仅是一个，您可以只删除冲突，这只是排列，并放弃整个链接）。
现在，如果您的搜索集是 4 个字符长，例如A, B, C, D，那么作为一个幼稚的搜索，您检查以下哈希以查看它们是否已包含在字典中：
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-combinations 然后 (M-1)-combinations 等。一旦找到匹配项，您就可以停止！您可能只会覆盖搜索空间的一小部分，最坏的情况可能是一半。
2) 首先搜索较短的匹配项（1-combos、2-combos 等）。假设您在第 2 级想出了一个未命中（例如，您的字典中没有字符串仅由Aand组成B）。使用辅助数据结构（可能是位图），它允许您检查字典中的任何单词是否部分由A和组成B（与检查完整组成的主哈希表相反）。如果您也错过了辅助位图，那么您知道您可以跳过所有更高级别的组合，包括Aand B（即您可以跳过hash(ABC), hash(ABD), andhash(ABCD)因为没有单词同时包含Aand B）。这利用了Apriori原则，并且随着 M 的增长和未命中变得更加频繁，将大大减少搜索空间。编辑：我意识到我抽象出的与“辅助数据结构”相关的细节很重要。当我更多地思考这个想法时，我意识到它倾向于将完整的字典扫描作为一个子过程，这违背了整个方法的要点。不过，这里似乎应该有一种使用Apriori原理的方法。
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 在其标准库中都没有。
首先要注意的是，您可以完全忽略字母顺序。
试一试（好吧，有点像特里），如下所示：
像这样构建树：
对于每个单词，对该单词的字母进行排序并将排序后的字母插入到 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
Trie：（只显示非空子）
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 } 等。因此，树包含可以用这些字母组成的每个可能的单词。
遍历列表中的每个单词并将其与树匹配。如果匹配是最大长度（使用所有字母），你就完成了。如果单词小于 max，但比任何先前匹配的单词长，请记住，这是“迄今为止最长的单词”（LWSF）。忽略长度小于 LWSF 的任何单词。此外，忽略任何超过字母列表长度的单词。
这是一个构建字母树后的线性时间算法，因此只要单词列表明显大于字母树，它是最快的方法。
我试图用 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 ;
}
}
}
}