google-code-prettify

Saturday, 1 December 2012

Are all characters in a string unique?

Here are some Java implementations checking if all the characters in a string are unique. The first solution uses HashMap to store the characters of the string:

boolean hasAllUniqueChars(String str) {
    HashMap<Character, Object> hashMapChars = new HashMap<Character, Object>();
    for (int i = 0; i < str.length(); i++) {
        if (hashMapChars.containsKey(str.charAt(i))) {
            return false;
        } else {
            hashMapChars.put(str.charAt(i), null);
        }
    }
    return true;
}

The second one is the most trivial one and has time complexity O(n2). It uses two nested for loops:

boolean hasAllUniqueChars2(String str) {  
    for (int i = 0; i < str.length(); i++) {
        for (int j = 0; j < str.length(); j++) {
            if(i == j){
                continue;
            }
            if(str.charAt(i) == str.charAt(j)){
                return false;
            }
        }
    }
    return true;
}

3 comments:

  1. why don't you use hashset instead of hashmap?

    ReplyDelete
    Replies
    1. boolean hasAllUniqueChars(String str) {
      HashSet collection = new HashMap();
      for (int i = 0; i < str.length(); i++) {
      if (!collection.add(str.charAt(i))) {
      return false;
      }
      }
      return true;
      }

      Delete
    2. Ivo, you are absolutely right! HashSet is even better. Thanks!

      Delete