检查字符串是否包含唯一字符的最简单方法是什么？

Question

如果一个单词由独特的字母组成(不区分大小写),我需要检查Java.由于直接的解决方案很无聊,我想出了:

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

目前我最喜欢#2,似乎是最简单的方式.其他有趣的解决方案？

Answer 1

我不喜欢1. - 这是一个O(N ²)算法.你的2.大致是线性的,但总是遍历整个字符串.你的3.是O(N lg ₂ N),(可能)是一个相对较高的常数 - 可能几乎总是慢于2.

但是,我的偏好是当你试图在集合中插入一个字母时,检查它是否已经存在,如果是,你可以立即停止.给定字母的随机分布,这应该只需要扫描平均一半的字符串.

编辑:两个注释都是正确的,你希望扫描的字符串的哪个部分将取决于分布和长度 - 在某些时候字符串足够长,重复是不可避免的,并且(例如)一个字符短那个机会仍然很高.事实上,给定一个平坦的随机分布(即,集合中的所有字符同样可能),这应该与生日悖论密切相关,这意味着碰撞的可能性与可能的字符数量的平方根有关.字符集.例如,如果我们假设基本的US-ASCII(128个字符)具有相同的概率,那么我们将在大约14个字符处达到50%的碰撞几率.当然,在实际字符串中,我们可能期望它早于此,因为在大多数字符串中,ASCII字符不会与频率接近相等的任何地方一起使用.

Answer 2

选项2是三者中最好的 - 哈希比搜索更快.

但是,如果你有足够的内存,那么有一种更快的方法.

利用字符集受限且已经枚举的事实,并在检查每个字符时跟踪出现的内容和未出现的内容.

例如,如果您使用的是单字节字符,则只有256种可能性.在读取字符串时,您只需要256位来跟踪.如果出现字符0x00,则翻转第一位.如果出现字符0x05,则翻转第六位,依此类推.遇到已经翻转的位时,该字符串不是唯一的.

最糟糕的情况是O(min(n,m))其中n是字符串的长度,m是字符集的大小.

当然,正如我在另一个人的评论中看到的那样,如果n> m(即字符串的长度>字符集的大小),那么通过鸽子洞原则,有一个重复的字符,可以在O(1)时间内确定.