查找字符串中是其他字符串的前缀的字符串

Question

这是一道面试题。给定一些字符串，找到其中的前缀字符串。例如，给定 strings = {"a", "aa", "ab", abb"}，则结果为{"a", "ab"}。

最简单的解决方案是将字符串排序，并检查每对相邻的两个字符串，以确定第一个字符串是否是第二个字符串的前缀。算法的运行时间是排序的运行时间。

我猜还有另一种解决方案，使用trie数据结构，并具有O(N)的复杂度，其中N是字符串的数量。你能提供这样的算法吗？

- Michael

---

很抱歉，排序解决方案无法提供这样的运行时间。假设你有{"a", "aa", "aaa"} - 你可以在O(nlog(n))的时间内对它们进行排序，但是你仍然需要检查"a"是否是"aa"的前缀，以及"a"是否是"aaa"和"aa"的前缀 - 这将给你带来O(n^2)的时间复杂度。 - Archeg

@Michael，我提供了一个算法，我相信可以在O（N）的时间内解决你的问题，但是你从未对此发表评论。你认为我的解决方案正确吗？如果正确，请将其标记为正确答案，否则我想听听您的意见。 - Martinsos

Answer 1

我有一个与Trie相关的想法，复杂度为O(N): 首先，你从空的Trie开始。 接下来，你逐个添加单词到Trie中。 当你添加一个单词（我们暂且称之为Wi）到Trie中后，有两种情况需要考虑：

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）是一步。在开始时，trie为空。黑色箭头显示我们在该步骤中访问（添加）的节点。表示某些单词的最后一个字母的节点将该单词写在括号中。

在步骤1中，我们添加了单词aab。 在步骤2中，我们添加了单词aaba，识别出一种情况2（单词aab），并将单词aab添加到结果中。 在第3步中，我们添加了单词aa，识别出情况1，并将单词aa添加到结果中。

最后，我们得到了结果={aab、aa}，这是正确的。

- Martinsos

Answer 2

对于问题：字符串a是否是字符串b的子串，原始答案是正确的（读错了）。

使用字典树，您可以在第一次迭代中将所有字符串添加到其中，在第二次迭代中开始阅读每个单词，假设为w。如果您发现一个单词已经读完，但没有达到字符串终止符（通常是$），则会到达字典树中的某个节点v。
通过从v进行DFS，您可以获取所有以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|)。

您可以在第一次迭代中从字符串构建suffix tree，在第二次迭代中检查每个字符串是否是另一个字符串的非平凡条目（不是它本身）。
此解决方案的时间复杂度为O(n*|S|)

- amit

---

我猜基数树在这里也可以使用相同数量的操作。 - Archeg

就像Archeg所说的那样，基数树可以用来在Trie中节省空间。 - Justin