检查是否字符串包含唯一字符的最简单的方法？ [英] Easiest way of checking if a string consists of unique characters?

问题描述

我需要检查在Java中，如果一个字由独特的字母（不区分大小写）。由于直解是枯燥的，我想出了：

I need to check in Java if a word consists of unique letters (case insensitive). As straight solution is boring, I came up with:

1. 对于一个字符串检查每一个字符，如果的indexOf（炭）== lastIndexOf（字符）。
2. 添加的所有字符为的HashSet 并检查是否设置大小==字符串的长度。
3. 将一个字符串转换为字符数组，它的排序按字母顺序，循环遍历数组元素，并检查 C [I] == C [I + 1] 。

1. For every char in a string check if indexOf(char) == lastIndexOf(char).
2. Add all chars to HashSet and check if set size == string length.
3. Convert a string to a char array, sort it alphabetically, loop through array elements and check if c[i] == c[i+1].

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

Currently I like #2 the most, seems like the easiest way. Any other interesting solutions?

推荐答案

我不喜欢1 - 这是一个O（N ² ）算法。你2.大致是线性的，而是始终贯穿整个字符串。你3.为O（N LG电子 ₂ N），用（可能）相对较高的恒定的 - 可能几乎总是慢于2

I don't like 1. -- it's an O(N²) algorithm. Your 2. is roughly linear, but always traverses the entire string. Your 3. is O(N lg₂ N), with (probably) a relatively high constant -- probably almost always slower than 2.

我的preference，但是，会当您尝试插入一个字母进入设置，检查它是否已经present可以了，如果是，你可以立即停止。鉴于随机分布的字母，这应该需要扫描只有一半平均的字符串。

My preference, however, would be when you try to insert a letter into the set, check whether it was already present, and if it was, you can stop immediately. Given random distribution of letters, this should require scanning only half the string on average.

编辑：双方的意见是正确的，正是你希望扫描将取决于分布和长度字符串的一部分 - 在某些时候串足够长的重复是不可避免的，（例如）一字符短了，机会依然pretty的该死的高。事实上，给定一个平坦的随机分布（即，在该组中的所有字符都同样有可能的），这应该紧密贴合与生日悖论，意味着冲突的可能性是关系到在一个可能接受字符的​​数量的平方根字符集。只是举例，如果我们假设基本US-ASCII（128个字符）的概率相同，我们会达到一个碰撞的几率为50％左右，在14个字符。当然，在真正的字符串，我们也许可以期待它比更早，因为ASCII字符不会有接近相同的频率在多数串任何地方使用。

both comments are correct that exactly what portion of the string you expect to scan will depend on the distribution and the length -- at some point the string is long enough that a repeat is inevitable, and (for example) one character short of that, the chance is still pretty darned high. In fact, given a flat random distribution (i.e., all characters in the set are equally likely), this should fit closely with the birthday paradox, meaning the chance of a collision is related to the square root of the number of possible characters in the character set. Just for example, if we assumed basic US-ASCII (128 characters) with equal probability, we'd reach a 50% chance of a collision at around 14 characters. Of course, in real strings we could probably expect it sooner than that, since the ASCII characters aren't used with anywhere close to equal frequency in most strings.

这篇关于检查是否字符串包含唯一字符的最简单的方法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！