查找TreeSet中以给定前缀开头的字符串

Question

我试图找到以给定前缀开头的TreeSet<String>中的字符串。我发现前面的问题要求相同的东西— Searching for a record in a TreeSet on the fly —但给出的答案不适合我，因为它假设字符串不包括Character.MAX_VALUE，我的可以。

（答案有使用treeSet.subSet(prefix, prefix + Character.MAX_VALUE)，这给之间prefix（含）prefix + Character.MAX_VALUE（独家），其中就出来与prefix除了那些与prefix + Character.MAX_VALUE开始启动所有字符串。但在所有的字符串我情况下，我需要找到与prefix开始所有串，包括那些与prefix + Character.MAX_VALUE开始。）

我怎样才能做到这一点？

Answer 1

首先，我建议重新检查您的要求。 Character.MAX_VALUE是U + FFFF，它不是一个有效的Unicode字符，永远不会;所以我想不出你需要支持它的一个很好的理由。

但是，如果这个要求有一个很好的理由，那么你需要“增加”你的前缀来计算最大的字符串，它大于以你的前缀开头的所有字符串。例如，给定"city"，则需要"citz"。你可以做如下：

/** 
* @param prefix 
* @return The least string that's greater than all strings starting with 
*   prefix, if one exists. Otherwise, returns Optional.empty(). 
*   (Specifically, returns Optional.empty() if the prefix is the 
*   empty string, or is just a sequence of Character.MAX_VALUE-s.) 
*/ 
private static Optional<String> incrementPrefix(final String prefix) { 
    final StringBuilder sb = new StringBuilder(prefix); 

    // remove any trailing occurrences of Character.MAX_VALUE: 
    while (sb.length() > 0 && sb.charAt(sb.length() - 1) == Character.MAX_VALUE) { 
     sb.setLength(sb.length() - 1); 
    } 

    // if the prefix is empty, then there's no upper bound: 
    if (sb.length() == 0) { 
     return Optional.empty(); 
    } 

    // otherwise, increment the last character and return the result: 
    sb.setCharAt(sb.length() - 1, (char) (sb.charAt(sb.length() - 1) + 1)); 
    return Optional.of(sb.toString()); 
} 

要使用它，你需要使用subSet当上述方法返回一个字符串，并tailSet当它没有返回值：

/** 
* @param allElements - a SortedSet of strings. This set must use the 
*      natural string ordering; otherwise this method 
*      may not behave as intended. 
* @param prefix 
* @return The subset of allElements containing the strings that start 
*   with prefix. 
*/ 
private static SortedSet<String> getElementsWithPrefix(
     final SortedSet<String> allElements, final String prefix) { 

    final Optional<String> endpoint = incrementPrefix(prefix); 

    if (endpoint.isPresent()) { 
     return allElements.subSet(prefix, endpoint.get()); 
    } else { 
     return allElements.tailSet(prefix); 
    } 
} 

在看到它在行动：http://ideone.com/YvO4b3。