根据自然排序获取下一个字符串

Question

在Java中，类String实现了Comparable接口，这意味着String对象有一个总的排序方式。这个排序被称为类的自然排序(natural ordering)，而类的compareTo方法被称为它的自然比较方法(natural comparison method)。在数学意义上，String对象集合也是可数的。

我需要一个函数，根据String的自然排序方式，返回下一个String。

对于数学倾向的人来说，

function(X) = Y, where Y is such that: 1) X < Y
                                       2) for all Z, if X < Z, then Y <= Z.

你能想到一个适用于字符串的函数吗？（匹配正则表达式^[A-Za-z0-9]+$的字符串。我不关心，但你可以避免控制字符或任何可能导致编码问题、在XML中不合法、有换行符或类似“问题”字符的内容。）

- Cantor

---

在您的自然顺序中，"A" < "AA" < "AB" 吗？ - gawi

@gawi：这不是我的自然顺序；String实现了Comparable接口：String的compareTo……它是按字典顺序排列的。 - Cantor

那么我相信meriton的答案是正确的。 - gawi

Answer 1

String successor(String s) {
    return s + '\0';
}

或者使用您有限的字母表：

String successor(String s) {
    return s + '0';
}

因为'0'是所有合法字符中Unicode值最小的。

为什么需要这样做，任何人都可以猜测...可能有更少hacky的解决方案。

- meriton

---

"Test" < "TestA"，但是 "Tesz" < "TestA"，所以这不是解决方案。 - Colin Hebert

@gawi：这不是作业，只是一个hack。我有一个二分查找，返回第一条记录的索引；而不是编写一个返回最后一条记录索引的查找，我只是要找到下一个字符串的第一条记录。 - Cantor

"Tesz".compareTo("TestA") 返回 6，因此 "Tesz" > "TestA"。 - meriton

Answer 2

正如其他答案所指出的那样，字符串的后继是该字符串紧随其后的值为0的字符（在Java中，char是一个无符号整数值，[0,65535]）。

// returns the lexicographical successor of a string
public static String successor(String s) {
    return s + "\0";
}

以下摘自SortedSet文档的内容规定了使用这种确切的惯用法来处理String，并解释了为什么你会想要使用这样的后继方法：

Note: several methods return subsets with restricted ranges. Such ranges are half-open, that is, they include their low endpoint but not their high endpoint (where applicable). If you need a closed range (which includes both endpoints), and the element type allows for calculation of the successor of a given value, merely request the subrange from lowEndpoint to successor(highEndpoint). For example, suppose that s is a sorted set of strings. The following idiom obtains a view containing all of the strings in s from low to high, inclusive:

SortedSet<String> sub = s.subSet(low, high+"\0");

A similar technique can be used to generate an open range (which contains neither endpoint). The following idiom obtains a view containing all of the strings in s from low to high, exclusive:

SortedSet<String> sub = s.subSet(low+"\0", high);

请注意，尽管这种习惯用法仍然很棘手，但可能不总是容易计算出任何通用类型的后继（例如，如果只是SortedSet<Number>）。更精细的 API 是 NavigableSet<E>，它扩展了SortedSet<E>并定义了这些范围操作，以允许使用boolean标志对任何组合的开放或关闭端点。

相关问题

• 当只支持半开区间时，如何实现包含范围查询？（例如SortedMap.subMap）
• 在Java中，是否有可能为数字盒类型编写通用的+1方法？
• 索引范围的上限是否总是被假定为排除在外？

- polygenelubricants

Answer 3

不确定你为什么需要这样的东西...对某个东西进行暴力破解吗？ 无论如何，下面是一个非常原始的解决方案：

public static String getNextString(String input)
{
  if(input == null || input.trim().length() < 1)
  {
    return("0");
  }
  else
  {
    String trimmed = input.trim();
    int lastPos = input.length()-1;
    int last = (int) input.charAt(lastPos);
    last++;
    if(last > (int) 'z')
    {
      if(lastPos == 0)
      {
        return "00";
      }
      else
      {
        return getNextString(trimmed.substring(0,lastPos-1)) + "0";
      }
    }

  }
}

显然，可能会有错误，因为我是在回家的路上用手机打的这段代码...

- Mastermnd