找到给出集合的最长的单词
这是一个谷歌面试问题，我在网上找到了大多数使用HashMap或类似数据结构的答案。 我想尽可能找到使用Trie的解决方案。 有人可以给我一些提示吗？
这是一个问题：您将获得一个字典，其forms为每行包含一个单词的文件。 例如，
abacus deltoid gaff giraffe microphone reef qar 您还会收到一系列信件。 例如，
{a, e, f, f, g, i, r, q}.
任务是找到字典中可以用字母集拼写的最长单词。 例如，上面示例值的正确答案是“长颈鹿”。 （注意“礁石”不是一个可能的答案，因为这组字母只包含一个“e”。）
Java实现将是首选。
没有Java代码。 你可以自己解决这个问题。
假设我们需要做很多次，这就是我要做的事情：
-
我首先为字典中由26位组成的每个单词创建“签名”，如果单词包含一个（或多个）字母实例，则设置位[letter]。 这些签名可以编码为Java
int。 -
然后创建一个映射，将签名映射到具有该签名的单词列表。
要使用预先计算的地图进行搜索：
-
为要查找单词的字母集创建签名。
-
然后迭代映射的键，寻找键
(key & (~signature) == 0)。 这将为您提供一个“可能”的简短列表，其中不包含任何不在所需字母集中的字母。 -
迭代短列表，查找每个所需字母的正确数字的单词，记录最长的匹配。
笔记：
-
虽然主要搜索大致是字典中单词数量的
O(N)，但测试非常便宜。 -
这种方法的优点是需要相对较小的内存数据结构，（最有可能）具有良好的局部性。 这可能有助于加快搜索速度。
这是加快上面的O(N)搜索步骤的想法。
从上面的签名图开始，为包含特定对字母的所有单词创建（预计算）衍生图; 即一个用于包含AB的单词，用于AC，BC，…和YZ。 然后，如果您正在寻找包含（比如说）P和Q的单词，您只需扫描PQ衍生图。 这将使O(N)步骤减少大约26^2 …以额外地图的更多内存为代价。
这可以扩展到3个或更多字母，但缺点是内存使用量激增。
另一个潜在的调整是（以某种方式）将初始字母对的选择偏向于不经常发生的字母/对。 但这增加了前期开销，这可能比搜索较短列表所获得的（平均）节省更多。
我怀疑基于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的根节点开始，带有整个给定的字母集合。 对于集合中的每个字母，您尝试查找子节点。 如果有，则递归并从集合中删除该字母。 有一次你的信件收集将是空的（最好的情况下，所有信件都会消耗 – 你可以立即拯救，而不必继续穿越特里）或者没有其他任何剩余字母的孩子 – 在这种情况下你会删除节点本身，因为这是你的“最长匹配”。
如果您更改递归步骤以便并行访问所有子项，收集结果 – 并选择最长的结果并返回该结果，则可以很好地并行化。
首先，好问题。 面试官想看看你是如何解决这个问题的。 在这些问题中，您需要分析问题并仔细选择数据结构。
在这种情况下，我想到了两个数据结构： HashMaps和Tries 。 HashMaps不太合适，因为你没有想要查找的完整密钥（你可以使用基于地图的倒排索引，但你说你已经找到了这些解决方案）。 你只有零件 – 这是Trie最适合的地方。
因此，尝试的想法是，您可以在遍历树时忽略字典中不存在的字符分支。
在您的情况下，树看起来像这样（我省略了非分支路径的分支）：
*
一个
bacus
d
三角肌
G
一个
鱼叉
一世
长颈鹿
米
麦克风
[R
礁
q
QAR
因此，在此trie的每个级别，我们查看当前节点的子节点，并检查子节点的字符是否在我们的字典中。
如果是：我们在该树中更深入，并从我们的字典中删除孩子的角色
这一直持续到你打了一片叶子（没有孩子了），在这里你知道这个词包含这个词典中的所有字符。 这是一个可能的候选人。 现在我们想回到树中，直到找到我们可以比较的另一场比赛。 如果最新找到的匹配较小，则丢弃它，如果更长，这是我们现在可能的最佳匹配候选者。
有一天，重复将完成，你将得到所需的输出。
请注意，如果有一个最长的单词，则此方法有效，否则您必须返回候选人列表（这是面试中未知的部分，您需要询问面试官希望看到的解决方案）。
所以你需要Java代码，这里有一个简单的Trie和单个最长的单词版本：
public class LongestWord { class TrieNode { char value; List 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 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 ，它指导您完成决策并构建专门针对面试问题的算法。
免责声明：这不是一个特里解决方案，但我仍然认为这是一个值得探索的想法。
创建某种哈希函数，只考虑单词中的字母而不是它们的顺序（除了排列外，不应该发生冲突）。 例如， ABCD和DCBA都生成相同的散列（但ABCDD不生成）。 生成这样一个包含字典中每个单词的哈希表，使用链接来链接冲突（另一方面，除非你有严格的要求找到“所有”最长的单词而不只是一个，你可以只删除冲突，这只是排列，并放弃整个链接）。
现在，如果您的搜索集长度为4个字符，例如A, B, C, D ，则作为näive搜索，检查以下哈希值以查看它们是否已包含在字典中：
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 * -Tree 。 鉴于你的collections[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树库。
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()
保存字典的集合类型的选择与算法无关。 如果你应该实现一个特里，这是一回事。 否则，只需从适当的库中创建一个来保存数据。 Java和Groovy在我的标准库中都没有我所知道的。
我试图在C ++中编码这个问题..我创建了自己的哈希键，并完成了与给定字符的所有组合。
从最大长度到1的这些输入字符的所有组合
这是我的解决方案
#include "iostream" #include using namespace std; int hash_f(string s){ int key=0; for(unsigned int i=0;i0;i--) { if( ((i==n-1)&&indexes[i] m) break; for(int i=1;i0;i--){ r = combination_m_n(str, str.size(),i ,num); for(int i=0;i
假设一个大字典和一个少于10或11个成员的字母集（例如给出的例子），最快的方法是构建一个包含字母可以生成的单词的树，然后将单词列表与树匹配。 换句话说，你的字母树的根有七个子节点：{a，e，f，g，i，r，q}。 “a”的分支具有六个子节点{e，f，g，i，r，q}等。因此，树包含可以用这些字母制作的每个可能的单词。
浏览列表中的每个单词并将其与树匹配。 如果匹配是最大长度（使用所有字母），则完成。 如果单词小于max，但比任何先前匹配的单词长，请记住它，这是“迄今为止最长的单词”（LWSF）。 忽略任何长度等于LWSF的单词。 另外，请忽略任何长于字母列表长度的单词。
这是一个线性时间算法，一旦构造了字母树，所以只要单词列表明显大于字母树，它就是最快的方法。
首先要注意的是，您可以完全忽略字母顺序。
有一个特里（好吧，一种特里）如下：
- 从根，有26个孩子（最多），每个字母一个。
- 从每个非根节点开始，子节点等于大于或等于节点字母的字母数。
- 让每个节点存储所有可以使用（确切地）来自根路径中的字母的单词。
像这样构建trie：
对于每个单词，对该单词的字母进行排序并将排序后的字母插入到trie中（通过从根创建这些字母的路径），随时创建所有必需的节点。 并将该单词存储在最终节点。
如何查询：
对于给定的一组字母，查找所有字母子集（大多数希望不存在）并在遇到的每个节点输出单词。
复杂：
O(k!) ，其中k是提供的字母数。 伊克！ 但是可笑的是，特里的话语越少，路径就越少，所需的时间就越少。 k是提供的字母数 （应该相对较小），而不是trie中的字数。
实际上它可能更符合O(min(k!,n)) ，看起来好多了。 请注意，如果给你足够的字母，你将不得不查找所有单词，因此你必须在最坏的情况下做O(n)工作，因此，就最坏情况的复杂性而言，你不能做好多了。
例：
输入：
aba b ad da la ma
排序方式：
aab b ad ad al am
Trie :(只显示非空儿童）
root / \ ab /-/|\-\ abdlm | b
查找adb ：
- 从根…
- 去找孩子
- 去看孩子
b- 没有孩子，回来
- 去小孩
d- 在节点输出单词 –
ad和da - 没有孩子，回来
- 在节点输出单词 –
- 处理完所有字母，返回
- 去看孩子
- 去看孩子
b- 节点处的输出字 –
b - 不寻找孩子，因为只有孩子> =
b存在 - 没有孩子，回来
- 节点处的输出字 –
- 没有孩子，停下来