查找作为其他字符串前缀的字符串

Question

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

最简单的解决方案是对字符串进行排序,如果第一个字符串是第二个字符串的前缀,则检查每对两个后续字符串.算法的运行时间是排序的运行时间.

我想还有另一个解决方案,它使用a trie,并且具有复杂性O(N),其中N是字符串的数量.你能建议这样的算法吗？

Answer 1

关于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)是一步.一开始trie是空的.黑色箭头显示我们在该步骤中访问(添加)的节点.代表某个单词的最后一个字母的节点将该单词写在括号中.

1. 在步骤1中,我们添加单词aab.
2. 在步骤2中,我们添加单词aaba,识别一个案例2(单词aab)并添加单词aab到结果.
3. 在步骤3中,我们添加单词aa,识别案例1并在结果中添加单词aa.

最后我们得到result = {aab,aa}这是正确的.