用于查找一个字符串是否是另一个字符串的前缀的数据结构
这是一道面试题：设计一个数据结构来高效地执行以下操作：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"]
您会建议哪种数据结构？
This is an interview question: Design a data structure to perform the following operation efficiently: boolean isPrefix(String s1, String s2).
I guess we can create a multimap, which maps prefixes to their strings. For instance,
strings: "aa", "ab", "abc", "ba", "ca"
multimap: "a" -> ["aa", "ab", "abc"]
"aa" -> ["aa"]
"ab" -> ["ab", "abc"]
"abc" -> ["abc"]
"ba" -> ["ba"]
"ca" -> ["ca"]
Which data structure would you propose ?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
trie 数据结构似乎是一个显而易见的答案，但所述问题并不需要高级数据结构。简单的字符串比较就足够了，而且速度非常快。最终，如果您想验证一个字符串是否是另一个字符串的前缀，则必须比较相应位置的每个字符。没有任何数据结构可以消除逐个字符比较的需要。
话虽这么说，如果您在大量文本中搜索前缀，还有其他技术，例如Rabin-Karp 概率字符串匹配。
The trie data structure would seem like an obvious answer, but the problem as stated doesn't require an advanced data structure. A simple string comparison will suffice and would be very fast. Ultimately, if you want to validate that one string is a prefix of another, you will have to compare every character at corresponding positions. No data structure eliminates the need for the character-by-character comparison.
That being said, if you're searching for the prefix in a large body of text, there are other techniques such as Rabin-Karp probablistic string matching.
最有效的前缀信息存储可能是 trie。
在这种情况下，字符串对应于树中的节点，其中当一个字符串的节点位于树中另一个字符串的下方时，一个字符串将另一个字符串作为前缀。
The most effective storage for prefix information is probably the trie.
In this, the strings correspond to nodes in a tree where one string has another as a prefix exactly when its node is below the other in the tree.