Java – the easiest way to check whether a string consists of unique characters?

If a word consists of unique letters (case insensitive), I need to check Java Because the direct solution is boring, I came up with:

>For each string in the string, check indexof (char) = = lastIndexOf (char). > Add all characters to the HashSet and check that size = = string length. > Convert the string into a character array, sort alphabetically, cycle through the array elements, and check that C [i] = = C [I 1]

At present, I like #2 it best. It seems the simplest way Any other interesting solutions?

Solution

I don't like 1. – This is an O (N2) algorithm Your 2 It is roughly linear, but always traverses the entire string Your 3 Is O (n LG2 n), a relatively high constant – probably almost always slower than 2

However, when you try to insert a letter into the set and check whether it already exists, my preference is that you can stop immediately Given randomly assigned letters, this should only scan half the string on average

Edit: both comments are correct, and exactly which part of the string you expect to scan will depend on the distribution and length - in some cases, if the string is long enough, repetition is inevitable, (for example) if one character is insufficient, the chance is still high In fact, given a flat random distribution (that is, all characters in the set are equally possible), this should be closely related to the birthday paradox, which means that the chance of collision is related to the square root of the number of possible characters For example, if we assume basic us-ascii (128 characters) with the same probability, we will achieve a 50% collision probability at about 14 characters Of course, in a real string, we may be earlier than it, because ASCII characters are not used anywhere near the same frequency in most strings