找出一个单词是否可以成为词典中单词的开头

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

我使用TreeSet实现了字典。

TreeSet词典 String startString;

问题1

什么是找出是否startString是启动O在至少在字典中的单词的最有效方法是什么？

理念1

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

哪里startStringPlusOne是等于startString除了最后一个字符，这是在字母表下列之一。

实施例：

startString: hom 
startStringPlusOne: hon

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

问题2

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

理念2

我想用字符数组与字母与数组中的下列字符替换string最后一个字母。有没有更高效的方法？

来源

2013-01-23 Maverik

你不能只使用：''stringPlusOne.startsWith（string）'？ –

'char nextChar =（char）（currentChar + 1）;'。不需要数组。 –

我想如果你正在寻找一个有效的解决方案，trie会是你需要的。 – Jack

如果内存不是问题，我会试图存储两个字典。一个人把你的话放进另一个人，让你的话开始。

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-23 16:26:23 izb

也许从我的问题中不清楚，但我必须找出一个字符串是否可以成为我的字典中某些单词的开始。无论多少，无论哪一个。我只需要知道是否至少有一个词以'string'中的相同字符存储开始。我有一本包含超过200000字的字典。我不认为创建第二个字典的开头是有效的。不是在记忆方面，也不在研究时间方面。你同意吗？ – Maverik

把它看成一个巨大的查找表形式的大缓存。你拿你的子字符串，并做一个单一的查询与答案是/否。没有比这更有效率。 – izb

所以你建议我创建两个TreeSet，一个用于字典，另一个用于开始。我想这会比字典至少大5倍。你认为执行'startss.contains（key）'比'dictionary.subSet（string，strinPlusOne）.size> 0'更快吗？ – Maverik

找出一个单词是否可以成为词典中单词的开头

回答

相关问题