4

这是一道面试题。给定多个字符串，找到这样的字符串，它们是其他字符串的前缀。例如，给定strings = {"a", "aa", "ab", abb"}结果是{"a", "ab"}.

最简单的解决方案是对字符串进行排序并检查每对两个后续字符串是否第一个是第二个的前缀。算法的运行时间就是排序的运行时间。

我想还有另一种解决方案，它使用 a trie，并且有 complex O(N)，其中 N 是字符串的数量。你能推荐这样一个算法吗？

4

2 回答 2

6

关于 Trie，我有以下想法，复杂度 O(N)：你从空的 Trie 开始。你一个一个接一个单词，然后把单词加到 Trie 上。在向 Trie 添加一个词（我们称之为词 Wi）后，需要考虑两种情况：

  1. Wi 是您之前添加的一些单词的前缀。如果您在添加单词 Wi 时没有向 Trie 添加任何节点，则该陈述是正确的。在这种情况下，Wi 是前缀，也是我们解决方案的一部分。
  2. 之前添加的一些词是Wi的前缀。如果您通过表示之前添加的某个单词的结尾的节点（让我们调用那个单词 Wj），那么该语句是正确的。在这种情况下，Wj 是 Wi 的前缀，也是我们解决方案的一部分。

更多细节（伪代码）：

for word in words
    add word to trie
    if size of trie did not change then   // first case
        add word to result
    if ending nodes found while adding word   // second case
        add words defined by those nodes to result
return result

向 Trie 添加新词：

node = trie.root();
for letter in word
    if node.hasChild(letter) == false then   // if letter doesnt exist, add it
        node.addChild(letter)
    if letter is last_letter_of_word then   // if last letter of word, store that info
        node.setIsLastLetterOf(word)
    node = node.getChild(letter)    // move

在添加新单词时，您还可以检查是否通过了代表其他单词最后一个字母的任何节点。我描述的算法复杂度是 O(N)。另一个重要的事情是，这样你可以知道单词 Wi 前缀其他单词的次数，这可能很有用。

{aab, aaba, aa} 的示例：绿色节点是检测为案例 1 的节点。红色节点是检测为案例 2 的节点。每一列（trie）是一个步骤。在开始的时候尝试是空的。黑色箭头显示我们在该步骤中访问（添加）了哪些节点。代表某个单词的最后一个字母的节点将该单词写在括号中。

在此处输入图像描述

  1. 在第 1 步中，我们添加单词 aab。
  2. 在第 2 步中，我们添加单词 aaba，识别一个案例 2（单词 aab）并将单词 aab 添加到结果中。
  3. 在第 3 步中，我们添加单词 aa，识别案例 1 并将单词 aa 添加到结果中。

最后我们有 result = {aab, aa} 这是正确的。

于 2012-07-09T14:40:45.177 回答
3

最初的答案是正确的：是一个字符串a（误读b）的子字符串。

使用 trie，您可以在第一次迭代中简单地将所有字符串添加到其中，在第二次迭代中，开始阅读每个单词，让它成为w. 如果你找到一个你读完的单词，但没有到达字符串终止符（$通常），你到达v了 trie 中的某个节点。 通过从
执行DFSv，您可以获得w作为它们前缀的所有字符串。

高级伪代码：

t <- new trie
for each word w:
   t.add(w)
for each word w:
  node <- t.getLastNode(w)
  if node.val != $
     collection<- DFS(node) (excluding w itself)
     w is a prefix of each word in collection

注意：为了优化它，您可能需要做一些额外的工作：如果a是前缀b，并且b是前缀c，那么a是前缀c，所以 - 当你做 DFS 时，如果你到达某个已经搜索过的节点 -只需将其字符串附加到当前前缀即可。
尽管如此，由于可能存在二次可能性（"a", "aa", "aaa", ....），因此获得所有可能性需要二次时间。

原始答案：查找是否a是的子字符串b：

建议的解决方案以二次复杂度运行，您需要检查每两对，给您O(n* (n-1) * |S|).

您可以在第一次迭代中从字符串构建后缀树，并在第二次迭代中检查每个字符串是否是另一个字符串的重要条目（不是其本身）。
这个解决方案是O(n*|S|)

于 2012-07-09T14:33:15.397 回答