string - 将 trie 转换为反向 trie？

Question

假设我有一个 trie 包含多个字符串的数据结构。要在 trie 中查找字符串，我会从根开始，然后按顺序跟随标有字符串适当字符的指针，直到到达给定节点。

现在假设我想为同一组字符串构建一个“反向 trie”，而不是从 first 字符开始查找字符串，我会从开始查找字符串最后一个字符。

是否有一种有效的算法可以将尝试转化为反向尝试？在最坏的情况下，我总是可以列出 trie 中的所有字符串，然后将它们一次一个地插入到反向 trie 中，但似乎可能有更好、更聪明的解决方案。

Answer 1

但是如果您的排序标准是基于字符串的反向，则您的 trie 中的节点基本上是随机排序的。也就是说，给定序列 [aardvark, bat, cat, dog, elephant, fox]，它们是按字母顺序排列的，颠倒单词不会得到序列 [xof, tnahpele, god, tac, tab, kravdraa].

换句话说，没有比构建反向特里树“更聪明的解决方案”了。