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

Question

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

4

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

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

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

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

按大小对数组进行排序，将最长的单词放在前面
对于每个单词，将其分成所有可能的方式。也就是说，对于“test”，将其拆分为{“t”，“est”}，{“te”，“st”}和{“tes”，“t”}。
然后，对于每个配对，检查第一半和第二半是否都存在于数组中的其他位置。
通过返回符合条件3的第一个字符串来“短路”。

- Lin Ma

2

你目前做了什么？请发布你的当前代码。 - Andy Turner

4

此解决方案不适用于由三个单词构成的单词。 - Nir Alfasi

1

如果输入是：test，tester，输出应该是 tester 吗？或者如果输入是：abc，bcdef，输出应该是什么？ - Nishant Kumar

1

这个问题对我来说仍然不清楚。为什么你的输出中不包含 testertest 作为子字符串？ - piotrekg2

1

@LinMa 我可以给你一个例子，但是你不觉得自己尝试找到它会是一个很好的练习吗？ - Nir Alfasi

显示剩余5条评论

5个回答

4

Richard's answer在许多情况下都可以很好地工作，但如果字符串W中有许多段，每个段可以以多种不同的方式分解，则可能需要指数时间。例如，假设W是abcabcabcd，其他单词是ab、c、a和bc。那么W的前3个字母可以被分解为ab|c或a|bc...接下来的3个字母也是如此，以此类推，总共有2^3=8种可能的分解方式。

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的后缀从某个位置i开始是可分解的或不可分解的时，我们可以记录这一事实并稍后利用它来节省时间。例如，在测试前8个分解中的前4个后，我们知道从位置4（即abcabcd）开始的W的后缀是不可分解的。那么当我们尝试第5个分解时，即以ab开头的第一个分解时，我们首先问自己：W的剩余部分，即从位置3开始的后缀是否可分解？我们还不知道，因此我们尝试添加c以得到ab|c，然后我们问：W的剩余部分，即从位置4开始的后缀是否可分解？我们发现它已经被发现是不可分解的，因此我们可以立即得出结论，即以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 (i.e. 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 时，才会执行函数的主体。这些事实意味着函数的主体只会运行函数可以被调用的不同值 i 的次数。这些值最多有 |W|+1 个，即 O(n)，除递归调用外，对 f(i) 的调用最多需要 O(n) 的时间来遍历 Richard's trie，因此总的时间复杂度受到 O(n^2) 的限制。

- j_random_hacker

谢谢 j_random_hacker，今天我调试了Trie树代码并亲自动手了解了它。有一个快速的问题，比如说，如果我想为单词Python构建Trie树，我认为我应该像这样构建Trie/后缀树 (Python, ython, thon, ton, on 和 n)，这样对于任何输入字符串（例如，ython），我可以知道该字符串是否匹配原始长字符串的一部分（例如Python）。在示例代码中，它似乎只构建了一个逻辑结构Python，并且想知道您的代码中如何匹配后缀单词ython。 - Lin Ma

@LinMa：我正在“借用”Richard的trie技术。你不需要为此构建后缀树（或后缀trie）-- 你只需像他一样通过trie“跟随”当前单词中的字母即可。我所添加的真正内容是一种DP技术，称为记忆化，它可以存储和重复使用子问题的解决方案，而不是重新计算它们。 - j_random_hacker

2

我猜你可能会混淆哪些单词被分割了。排序后，你考虑逐个单词地处理，按长度递减的顺序。我们称正在尝试分解的单词为“候选单词”。如果候选单词由其他单词组成，则它肯定以一个单词开头，因此你需要将候选单词的所有前缀与所有可能的单词进行比较。在比较步骤中，你将候选单词的前缀与整个单词进行比较，而不是拆分后的单词。

顺便说一下，给定的解决方案对三个及以上的单词无效。修复方法如下:

- 尝试候选单词的每个前缀，并将其与所有单词进行比较 - 如果匹配，请使用后缀重复搜索

例子：

`testingtester` 给出前缀：

`t`, `te`, `tes`, `test`, `testi`, `testin`, `testing`, `testingt`, `testingte`, `testingtes` 和 `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

- user1196549

嗨，Yves，我不太理解这一步骤：“如果匹配，则使用后缀重复搜索”，为什么不能重复使用相同的前缀或与其他前缀重叠？对于重叠，我的意思是，例如A [0：3]可能匹配一个单词，而A [0：4]可能匹配另一个单词。 - Lin Ma

1

你需要使用所有匹配的前缀继续搜索。 - user1196549

谢谢Yves，为什么原始解决方案triwords不起作用？能否提供一个例子？ :) - Lin Ma

1

因为“second half”是一个双词，而不是一个单词。请尝试使用“testtesttesting”。 - user1196549

1

@LinMa：手动执行示例，你就会明白。 - user1196549

显示剩余6条评论

2

我会用递归来解决这个问题。从最长的单词开始，找到以它开头的单词。对于任何这样的单词，将其从原始单词中删除，并以相同的方式处理剩余部分。

伪代码：

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 开头。剩下的 = f。2. 没有找到以 f 开头的单词。
1. abcdef 以 abc 开头。剩下的 = def。2. 没有找到以 def 开头的单词。
1. abcdef 以 ab 开头。剩下的 = cdef。2. cdef 以 cde 开头。剩下的 = f。3. 没有找到以 f 开头的单词。
1. abcde 以 abc 开头。剩下的 = cde。2. 找到了 cde 本身。abcde 是一个由其他单词组成的单词。

- Thorsten Kettner

1

word = wordpart 这句话很清楚。一旦我们找到以'finger'开头的单词'fingerprint'，我们将检查剩余的部分'print'。在所有单词中有一个词 'print'，所以我们找到了一个 word = wordpart，并知道'fingerprint'是一个复合词。每次调用iscomposed时，我们也将原始单词命名为'fingerprint'，但是目的是为了检查我们是否处理整个单词还是部分单词。否则，每个单词都会被识别为复合词，因为它总是与自身匹配。（<> 表示“不等于”）。 - Thorsten Kettner

1

所以：我们从“指纹”开始。我们在allwords中找到“指纹”，但是我们知道可以忽略它（因为它是原始单词），然后我们找到“手指”（这不是原始单词）并对其进行处理。（然而，我刚刚注意到，在“elseif”中我忘记了做同样的事情，所以我现在会更正这个错误。） - Thorsten Kettner

1

在搜索匹配项时，原始单词仅用于排除列表中的单词。我们可以使用标志，或者为了更好的性能甚至使用allwords中的位置，以便仅在该位置之后开始搜索。第一次调用：iscomposed（'fingerprint'，'fingerprint'）。当我们在列表中找到单词“part”时，我们不能返回“yes”，因为“fingerprint”实际上不是“fingerprint”的一部分。第二次调用：iscomposed（'fingerprint'，'print'）。当我们在列表中找到“print”时，我们必须返回“yes”，因为“print”是“fingerprint”的一个真正的单词部分。 - Thorsten Kettner

1

关于“短路”解决方案：是的，我认为我理解了。您将“指纹”分成所有可能的部分，并排除除{'finger'，'print'}之外的所有部分，因为这是唯一一个第一部分和最后一部分都是单词的组合。但是，我认为您的示例过于简化了。一个单词可以由两个或更多单词组成。因此，您必须将“指纹”拆分为两个、三个、四个、五个等成对的部分。这必须是数百种组合。对于每个组合，您都必须在列表中查找单词。为了进行“短路”，需要进行数百次搜索。 - Thorsten Kettner

1

嗨，我从未使用过Trie树，所以无法帮助你。到目前为止，我甚至还没有考虑实际的字符串搜索，只是主要算法。现在想想，我想我会在我的算法中对按字母顺序排序的列表使用二分查找，而在你的算法中可能会使用哈希技术，因为你只需要寻找完整的单词。（例如，对于“test”，你将查找“t”、“te”和“tes”（并发现这些都不是单词），而我将查找所有以“test”开头的单词（只有“test”本身，所以也没有找到）。 - Thorsten Kettner

显示剩余15条评论

0

使用递归查找最长的单词

class FindLongestWord {

public static void main(String[] args) {
    List<String> input = new ArrayList<>(
            Arrays.asList("cat", "banana", "rat", "dog", "nana", "walk", "walker", "dogcatwalker"));

    List<String> sortedList = input.stream().sorted(Comparator.comparing(String::length).reversed())
            .collect(Collectors.toList());

    boolean isWordFound = false;
    for (String word : sortedList) {
        input.remove(word);
        if (findPrefix(input, word)) {
            System.out.println("Longest word is : " + word);
            isWordFound = true;
            break;
        }
    }
    if (!isWordFound)
        System.out.println("Longest word not found");

}

public static boolean findPrefix(List<String> input, String word) {

    boolean output = false;
    if (word.isEmpty())
        return true;
    else {
        for (int i = 0; i < input.size(); i++) {
            if (word.startsWith(input.get(i))) {
                output = findPrefix(input, word.replace(input.get(i), ""));
                if (output)
                    return true;
            }
        }
    }
    return output;

}

}

- Ghanshyam Vaghela

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Richard · Accepted Answer

间接回答你的问题，我认为以下是使用tries解决此问题的有效方法。

从字符串中的所有单词构建一棵trie树。

按照最长单词在前的顺序对单词进行排序。

现在，对于每个单词W，从trie树的顶部开始，并使用来自正在测试的单词的字母一次跟随树向下移动一个字母。

每当一个单词结束时，从顶部递归重新进入trie树，做个记号表示你已经“分支”。如果你在单词末尾用完了字母并且已经分支，那么你就找到了一个复合词，并且因为单词是排序过的，这是最长的复合词。

如果在任何时候字母不匹配，或者你用完了字母并且没有到达单词的末尾，只需回溯到分支的地方并继续前进即可。

很抱歉我不太懂Java，所以无法提供该语言的示例代码。但是，我已经用Python编写了一个解决方案（使用this answer中的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

考虑到上述内容，你原来的问题的答案变得更加清晰明了：我们事先不知道哪些前缀词的组合可以成功地遍历整棵树。因此，我们需要准备好检查所有可能的前缀词组合。

由于你找到的算法没有有效的方法来确定一个单词的子集是否为前缀，它会在单词的所有可能分割点处进行分割，以确保生成所有的前缀。