4

我必须找出给定的单词是否可以成为字典中其他单词的开头。

我使用 TreeSet 实现了字典。

TreeSet 字典 String startString;

问题 1

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

理念一

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

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

例子：

startString: hom
startStringPlusOne: hon

通过这种方式，它SubSet返回一个空集，这意味着它string不是字典中单词的开头。

问题 2

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

想法 2

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

4

1 回答 1

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 时删除键。如果您不需要这样做，那么您不需要存储该数字。

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

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

就速度而言，这似乎是最有效的，但以牺牲内存效率为代价（这可能不是值得担心的问题）。

于 2013-01-23T16:26:23.350 回答