java - 找出一个单词是否可以作为字典中单词的开头

Question

我必须查明给定的单词是否可以作为字典中其他单词的开头。

我使用 TreeSet 实现了字典。

TreeSet字典 字符串开始字符串；

问题一

找出 startString 是否至少是字典中一个单词的开头的最有效方法是什么？

想法一

我的想法是使用dictionary.subSet(startString, startStringPlusOne);

其中 startStringPlusOne 等于 startString 除了最后一个字符，即字母表中的下一个字符。

例子:

startString: hom
startStringPlusOne: hon

在这种情况下，SubSet 返回一个空集，这意味着 string 不是字典中单词的开头。

问题2

计算 stringPlusOne 的最有效方法是什么？

想法 2

我想使用一个包含字母表字母的字符数组，并将 string 的最后一个字母替换为数组中的以下字符。有没有更有效的方法？

Answer 1

如果内存不是问题，我很想存储两本字典。将您的单词放入其中，将单词的开头放入另一个。

1)
["aardvark", "banana", "band"]

2)
{
    "aardvar" => 1,
    "aardva" => 1,
    "aardv" => 1,
    "aard" => 1, 
    "aar" => 1, 
    "aa" => 1, 
    "a" => 1, 
    "banan" => 1, 
    "bana" => 1, 
    "ban" => 2, 
    "ba" => 2, 
    "b" => 2
}

那么问题的答案是“有没有以‘ban’开头的单词？”是“是的，有2”。您的问题没有说明是否有必要找出这些词是什么。

只有当您需要从字典中删除单词时，计数才会真正有用。如果是这样，您将需要减少计数并在它们达到 0 时删除 key 。如果您不需要这样做，则不需要存储该数字。

如果您需要回答“哪些词以‘ban’开头？”这个问题，那么您需要存储对这些词的引用，而不仅仅是计数，例如

"ban" => ["banana", "band"]

这在速度方面似乎是最有效的，但以内存效率为代价(这可能不是一个值得担心的问题)。