查找一个字符串是否为另一个字符串的数据结构

这是一个面试问题：设计一个数据结构来高效地执行以下操作：boolean isPrefix(String s1, String s2)。查找一个字符串是否为另一个字符串的数据结构

我想我们可以创建一个multimap，它将前缀映射到它们的字符串。例如，

strings: "aa", "ab", "abc", "ba", "ca" 
multimap: "a" -> ["aa", "ab", "abc"] 
      "aa" -> ["aa"] 
      "ab" -> ["ab", "abc"] 
      "abc" -> ["abc"] 
      "ba" -> ["ba"] 
      "ca" -> ["ca"]

你会提出哪种数据结构？

来源

2012-01-02 Michael

为什么不使用trie？ http://en.wikipedia.org/wiki/Trie – phimuemue 2012-01-02 11:08:19

我不知道我是否明白你的意思是“有效”。该问题具有o（n）的时间复杂度 - 您提出的解决方案是在空间复杂度为o（exp（n））的情况下进行交易，以再次获得o（n）的时间复杂度。查找“a”并在结果列表中搜索S2？ – 2012-01-02 11:10:34

你的实际问题如下？你有一大堆字符串，你想对这些字符串做一些预处理，这样连续调用'isPrefix'的速度非常快。因为这个问题 - 正如你所说的 - 通过比较两个字符串s1'和's2'是可以解决的。 – phimuemue 2012-01-02 11:15:09

trie数据结构似乎是一个明显的答案，但所述的问题不需要高级数据结构。一个简单的字符串比较就足够了，而且会非常快。最终，如果你想验证一个字符串是另一个字符串的前缀，你将不得不比较每个字符在相应的位置。没有数据结构消除了逐个字符比较的需要。

话虽如此，如果您在搜索作为大量文本的前缀，还有其他技术，如Rabin-Karp probablistic string matching。

来源

2012-01-02 11:13:37

最有效的前缀信息存储可能是trie。

在此，字符串对应于树中的节点，其中一个字符串恰好在树的节点低于另一个字符串时具有另一个字符串作为前缀。

来源

2012-01-02 11:08:47

查找一个字符串是否为另一个字符串的数据结构

回答

相关问题