找到由其他单词组成的最长单词

Question

我正在解决一个问题，即编写一个程序来查找单词列表中由其他单词组成的最长单词。

EXAMPLE
Input: test, tester, testertest, testing, testingtester
Output: testingtester

我搜索并找到了以下解决方案，我的问题是我在第 2 步中感到困惑，为什么我们应该以所有可能的方式打破每个单词？为什么不直接将每个单词作为一个整体使用？如果有人可以提供一些见解，那就太好了。

下面的解决方案执行以下操作：

1. 按大小对数组进行排序，将最长的单词放在最前面
2. 对于每个单词，以所有可能的方式将其拆分。即对于“test”，将其拆分为{“t”, “est”}, {“te”, “st”}和{“tes”, “t”}。
3. 然后，对于每个配对，检查前半部分和第二部分是否都存在于数组中的其他地方。
4. 通过返回我们找到的符合条件 #3 的第一个字符串来“短路”。

Answer 1

间接回答您的问题，我相信以下是使用尝试解决此问题的有效方法。

从字符串中的所有单词构建一个尝试。

对单词进行排序，使最长的单词排在最前面。

现在，对于每个单词 W，从树的顶部开始，并使用您正在测试的单词中的字母，一次一个字母地沿着树向下跟随单词。

每次单词结束时，从顶部递归地重新输入特里树，记下您已经“分支”。如果单词末尾的字母用完并进行了分支，则您找到了一个复合词，并且由于单词已排序，因此这是最长的复合词。

如果字母在任何时候停止匹配，或者你用完了并且不​​在单词的末尾，只需回到你分支的地方并继续插入。

恐怕我不太了解 Java，所以我无法为您提供该语言的示例代码。但是，我已经用 Python 写出了一个解决方案（使用这个答案中的 trie 实现）。希望你清楚：

#!/usr/bin/env python3

#End of word symbol
_end = '_end_'

#Make a trie out of nested HashMap, UnorderedMap, dict structures
def MakeTrie(words):
  root = dict()
  for word in words:
    current_dict = root
    for letter in word:
      current_dict = current_dict.setdefault(letter, {})
    current_dict[_end] = _end
  return root

def LongestCompoundWord(original_trie, trie, word, level=0):
  first_letter = word[0]
  if not first_letter in trie:
    return False
  if len(word)==1 and _end in trie[first_letter]:
    return level>0
  if _end in trie[first_letter] and LongestCompoundWord(original_trie, original_trie, word[1:], level+1):
    return True
  return LongestCompoundWord(original_trie, trie[first_letter], word[1:], level)

#Words that were in your question
words = ['test','testing','tester','teste', 'testingtester', 'testingtestm', 'testtest','testingtest']

trie = MakeTrie(words)

#Sort words in order of decreasing length
words = sorted(words, key=lambda x: len(x), reverse=True)

for word in words:
  if LongestCompoundWord(trie,trie,word):
    print("Longest compound word was '{0:}'".format(word))
    break

考虑到上述内容，您原来问题的答案变得更加清晰：我们不知道哪些前缀词组合将带我们成功地通过树。因此，我们需要准备检查所有可能的前缀词组合。

由于您发现的算法没有一种有效的方法来知道单词的哪些子集是前缀，它会在单词中的所有可能点拆分单词以确保生成所有前缀。