java - 在 TreeSet 中查找包含前缀的条目

Question

我在 Java 中有一个包含字符串(特别是单词)的 TreeSet。我需要写一个方法...

public boolean isValidPrefix(String prefix)

...它接受前缀作为参数并检查 TreeSet 以查看其包含的任何单词是否以该前缀开头。

例如，给定前缀 "CA" 和包含 {"DOG,"CAT","COW"} 的 TreeSet，我的方法需要识别有一个单词 “CAT” 以前缀开头。

P.S. 我会遍历 TreeSet，但时间复杂度是一个明显的限制，因为在许多情况下 TreeList 将多达 200,000 个单词。

Answer 1

如果一个字符串 foo 是 TreeSet 中另一个字符串 bar 的前缀，我认为 bar 紧跟在 TreeSet 中的 foo 之后是一个安全的假设。

因此，我认为采取 TreeSet.ceiling(foo) 就足够了并检查 foo 是否是它的前缀。

从该函数的文档中，我们看到它准确地返回将按顺序跟在给定元素之后的元素。

Returns the least element in this set greater than or equal to the given element, or null if there is no such element.

算法因此是:

1. 在输入上调用 TreeSet.ceiling()。如果返回值为null，则返回false。
2. 如果返回值不为null，则返回输入是否为返回值的有效前缀。