检查字符串是否由唯一字母组成的最简单方法？

Question

如果一个单词由唯一的字母(大小写不敏感)组成，我需要在Java中签入。由于直截了当的解决办法很无聊，我想出了：

1. 对于字符串中的每个字符，检查是否为indexOf(char) == lastIndexOf(char)。
2. 将所有字符添加到HashSet中，并检查是否设置了==字符串长度。
3. 将字符串转换为char数组，按字母顺序排序，遍历数组元素并检查是否为c[i] == c[i+1]。

目前我最喜欢的是#2，似乎是最简单的方法。还有其他有趣的解决方案吗？

Answer 1

选项2是三种方法中最好的一种--散列比搜索快。

但是，如果您有足够的内存，还有一个更快的方法。

利用字符集有限且已经枚举的事实，在检查每个字符时跟踪出现了什么和没有显示什么。

例如，如果您使用的是单字节字符，则只有256种可能性。在读取字符串时，只需要256位就可以保持跟踪。如果出现字符0x00，请翻转第一个位。如果出现字符0x05，则翻转第六位，以此类推。当遇到一个已经翻转的位时，字符串并不是唯一的。

最坏的情况是O(min(n，m))，其中n是字符串的长度，m是字符集的大小。

当然，正如我在另一个人的评论中所看到的，如果n>m(即字符串长度>字符集的大小)，那么根据鸽子洞原理，就有一个重复的字符，可以在O(1)时间内确定。

Answer 2

我喜欢HashSet的想法。它在概念上很简单，只有一次通过字符串。要进行简单的性能改进，请检查添加返回值。有一件事你应该知道，这是通过案例折叠工作。朝一个方向。您可以围绕字符创建一个包含不同等号语义的包装类，以真正区分大小写。

有趣的是，Apache有一个CaseInsensitiveMap (src)，它的工作方式是上大小写然后下大写键.您可能知道，Java的HashSet是由一个HashMap支持的。

public static boolean allUnique(String s)
{
  // This initial capacity can be tuned.
  HashSet<Character> hs = new HashSet<Character>(s.length());
  for(int i = 0; i < s.length(); i++)
  {
    if(!hs.add(s.charAt(i).toUpperCase())
      return false;
  }
  return true;
}

Answer 3

你所说的“独特字母”是指26的标准英语集合，还是允许有趣的Unicode？如果字符串包含非字母，您期望得到什么结果？

如果您只考虑26个可能的字母，并且您想忽略任何非字母或认为它是自动失败，最好的算法可能是这个伪代码：

create present[26] as an array of booleans.
set all elements of present[] to false.
loop over characters of your string
  if character is a letter
    if corresponding element of present[] is true
      return false.
    else
      set corresponding element of present[] to true.
    end if
  else
    handle non-letters
  end if
end loop

剩下的唯一问题是，您的数组实际上应该是数组(要求26个操作为零)，还是一个位字段(可能需要更多的工作来检查/设置，但可以在单个操作中为零)。我认为位字段访问将与数组查找相当，如果不是更快的话，所以我希望位字段是正确的答案。