找到由其他单词构成的最长单词
我正在研究一个问题，即编写一个程序来查找单词列表中由其他单词组成的最长单词。
EXAMPLE Input: test, tester, testertest, testing, testingtester Output: testingtester 我搜索并找到以下解决方案，我的问题是我在第2步中感到困惑，为什么我们应该以各种可能的方式打破每个单词？ 为什么不直接使用每个单词呢？ 如果有人能提供一些见解，那就太好了。
以下解决方案执行以下操作：
- 按大小对数组进行排序，将最长的单词放在前面
- 对于每个单词，请以所有可能的方式将其拆分。 也就是说，对于“test”，将其分为{“t”，“est”}，{“te”，“st”}和{“tes”，“t”}。
- 然后，对于每个配对，检查前半部分和第二部分是否都存在于arrays中的其他位置。
- 通过返回我们发现符合条件＃3的第一个字符串来“短路”。
间接回答你的问题，我相信以下是使用try解决这个问题的有效方法。
根据字符串中的所有单词构建一个trie。
对单词进行排序，使最长的单词排在第一位。
现在，对于每个单词W，从trie的顶部开始，然后使用您正在测试的单词中的字母一次一个字母地在树下面开始跟随单词。
每当一个单词结束时，递归地从顶部重新输入trie，记下你已经“分支”。 如果单词末尾的字母用完并且已经分支，那么你找到了一个复合词，因为单词被排序，这是最长的复合词。
如果字母在任何时候停止匹配，或者你用完了并且不在单词的末尾，只需回溯到你分支的任何地方并继续插入。
我担心我不太了解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
考虑到上述情况，您原始问题的答案变得更加清晰：我们事先并不知道前缀词的哪个组合将成功通过树。 因此，我们需要准备好检查所有可能的前缀词组合。
由于您找到的算法没有一种有效的方法来知道单词的哪些子集是前缀，因此它会在单词中所有可能的点处拆分该单词以确保生成所有前缀。
我想你只是在混淆哪些单词被分开了。
排序后，您可以通过减少长度来逐个考虑单词。 让我们称一个“候选人”为您要分解的词。
如果候选人是由其他单词组成的，那么它肯定以一个单词开头，因此您将比较候选人的所有前缀与所有可能的单词。
在比较步骤中，您将候选前缀与整个单词进行比较，而不是分割单词。
顺便说一句，给定的解决方案不适用于三字和更长时间。 修复方法如下：
- 尝试候选人的每个前缀，并将其与所有单词进行比较
- 如果匹配，请使用后缀重复搜索。
例：
testingtester给出了前缀
t ， te ， tes ， test ， testi ， testi ， testing ， testi ， testi ， testi和testingteste
其中， test和testing都是单词。 然后你需要尝试相应的后缀ingtester和tester 。
ingtester给出
i ， in ， ing ， ingt ， ingte ， ingtes ， ingtest和ingteste ，其中没有一个是单词。
tester是一个词，你完成了。
IsComposite(InitialCandidate, Candidate): For all Prefixes of Candidate: if Prefix is in Words: Suffix= Candidate - Prefix if Suffix == "": return Candidate != InitialCandidate else: return IsComposite(InitialCandidate, Suffix) For all Candidate words by decreasing size: if IsComposite(Candidate, Candidate): print Candidate break
我可能会在这里使用递归。 从最长的单词开始，找到它开头的单词。 对于任何这样的单词，将其从原始单词中删除，并以相同的方式继续其余部分。
伪代码：
function iscomposed(orininalword, wordpart) for word in allwords if word <> orininalword if wordpart = word return yes elseif wordpart starts with word if iscomposed(orininalword, wordpart - word) return yes endif endif endif next return no end main sort allwords by length descending for word in allwords if iscomposed(word, word) return word next end
例：
话： ABCDEF ABCDE ABC CDE AB
关：
1. abcdef以abcde开头。 rest= f。 2.找不到单词f。 1. abcdef以abc开头。 rest= def。 2.找不到单词def开头。 1. abcdef以ab开头。 rest = cdef。 2. cdef以cde开头。 rest= f。 3.找不到单词f。 1. abcde以abc开头。 rest = cde。 2. cde本身找到了。 abcde是一个组成单词
理查德的答案在许多情况下都能很好地运作，但它可能需要指数时间：如果字符串W有很多段，每个段都可以用多种不同的方式分解，就会发生这种情况。 例如，假设W是abcabcabcd ，其他词是ab ， c ， a和bc 。 然后W的前3个字母可以分解为ab|c或a|bc …接下来的3个字母和接下来的3个字母，对于2 ^ 3 = 8个可能的前9个字母的分解：
a|bc|a|bc|a|bc a|bc|a|bc|ab|c a|bc|ab|c|a|bc a|bc|ab|c|ab|c ab|c|a|bc|a|bc ab|c|a|bc|ab|c ab|c|ab|c|a|bc ab|c|ab|c|ab|c
所有这些部分分解最终都必然失败，因为输入中没有包含W的最终字母d单词 – 但是他的算法会在发现之前探索它们。 通常，由n个拷贝的abc后跟单个d组成的单词将花费O（n * 2 ^ n）时间。
我们可以通过记录关于W的后缀的可分解性的额外信息来改进这个O（n ^ 2）最坏情况时间（以O（n）空间为代价） – 也就是W的后缀我们已经发现我们可以或不能匹配单词序列。 这种算法称为动态编程 。
我们需要某些字W可被分解的条件正是W从其他字的集合开始用一些字X开始， 并且从位置| X | +1开始的W的后缀是可分解的 。 （我在这里使用基于1的索引，我将表示字符串S的子字符串，从位置i开始，到位置j由S [i..j]结束。）
每当我们发现在某个位置开始的当前单词W的后缀是或者不可分解时，我们就可以记录这个事实，并在以后使用它来节省时间。 例如，在测试前面列出的8中的前4个分解之后，我们知道从位置4开始的W的后缀（即abcabcd ）是abcabcd 。 然后，当我们尝试第5次分解时，即第一次以ab开始时，我们首先提出一个问题：W的其余部分，即从位置3开始的W的后缀，是否可以分解？ 我们还不知道，所以我们尝试添加c来获得ab|c ，然后我们问：W的其余部分，即从第4位开始的W的后缀，是否可以分解？ 并且我们发现它已经被发现不是 – 所以我们可以立即得出结论，不可能从ab|c开始分解W，而不是必须研究所有4种可能性。
假设当前字W是固定的，我们想要构建的是函数f（i），其确定从位置i开始的W的后缀是否是可分解的。 伪代码可能如下所示：
- Build a trie the same way as Richard's solution does. - Initialise the array KnownDecomposable[] to |W| DUNNO values. f(i): - If i == |W|+1 then return 1. (The empty suffix means we're finished.) - If KnownDecomposable[i] is TRUE or FALSE, then immediately return it. - MAIN BODY BEGINS HERE - Walk through Richard's trie from the root, following characters in the suffix W[i..|W|]. Whenever we find a trie node at some depth j that marks the end of a word in the set: - Call f(i+j) to determine whether the rest of W can be decomposed. - If it can (ie if f(i+j) == 1): - Set KnownDecomposable[i] = TRUE. - Return TRUE. - If we make it to this point, then we have considered all other words that form a prefix of W[i..|W|], and found that none of them yield a suffix that can be decomposed. - Set KnownDecomposable[i] = FALSE. - Return FALSE.
调用f（1）然后告诉我们W是否可分解。
当调用f（i）返回时，KnownDecomposable [i]已被设置为非DUNNO值（TRUE或FALSE）。 仅当KnownDecomposable [i]为DUNNO时，才会运行该函数的主体。 这些事实共同意味着函数的主体将只运行多次，因为可以调用函数。 最多| W | +1这样的值，即O（n），并且在递归调用之外，对f（i）的调用最多花费O（n）时间来遍历Richard的trie，所以整体上是时间复杂性受O（n ^ 2）的限制。