string - 将 trie 转换为反向 trie？

Question

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

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

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

Answer 1

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

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