时间和空间效率字典实现

我试图在Java中创建一个通用字符字典的空间和时间效率实现。

字典不是按a - z排序，而是以某种方式将包含字母"a"、"B"等的所有单词组合在一起。应用程序需要能够删除包含用户输入的任何字母的所有单词。因此，如果用户输入"L"，所有包含"L"的单词都会被删除。

我创建了:

Set dictionary -存储所有的单词。

Map<性格,Set>> -将字符A映射到Z，每个字符都有一个集合，其中包含字典中包含该字母的所有单词。

的例子:

dictionary {"AAB", "ABB", "BBC", "BBA", "CBB"}

地图:

A - "AAB", "ABB", "BBA" 
B - "AAB", "ABB", "BBC", "BBA", "CBB"
C - "BBC", "CBB"

如果用户选择"A"，则从字典中删除A的集合并重建地图，等待用户删除另一个字母。

我的问题是这会导致大量的数据重复和效率低下。我想不出其他有效实现这一目标的方法。有人暗示树可能是解决这个问题的一种方法，但我看不出它们的执行如何在时间和精力上都更有效。空间。

非常感谢您的帮助

听起来应该使用trie。这是一个非常简单的树状结构，细节和实现示例可以在wikipedia上找到:

根据您的需要，您可以使用后缀压缩或打包来进一步提高空间效率(注意，完成这些之后，您的树将不再是可修改的)。

另外，我还会考虑是否必须从字典结构中删除与给定前缀不匹配的所有项。通过尝试，您可以通过简单地"查看"相关子树并仅考虑这些条目来消除无效单词。

希望有所帮助

相关内容