Skip to content

Instantly share code, notes, and snippets.

@Jeffwan
Created February 7, 2014 04:06
Show Gist options
  • Save Jeffwan/8857242 to your computer and use it in GitHub Desktop.
Save Jeffwan/8857242 to your computer and use it in GitHub Desktop.
Implement an algorithm to determine if a string has all unique characters. CC 150 - Arrays and Strings
package CC150.ArraysAndString;
import java.util.HashSet;
import java.util.Set;
public class IsUniqueChars {
public static void main(String args[]) {
System.out.println(isUniqueChars("abcdefghijklmnopqrstuvwxyz"));
}
/**
* Book's solution, just use boolean[] replaces Set, I need to understand unique characters!
* Then I could know I can create to boolean[256] to flag exist character.
*
* In additon, no need to conver string to charArray,just use charAt(), save some space
*
* Conclusion: 1.understand unicode & ascII character.(only 256 characters) 2. study using boolean[] as flag
* In my solution, I just judge str == null and str.length() ==0 but not use str.length() >256
*
*/
public static boolean isUniqueChars(String str) {
if (str.length() > 256) {
return false;
}
boolean[] flag = new boolean[256];
char temp;
for (int i=0; i<str.length(); i++) {
temp = str.charAt(i);
if(flag[temp]) {
return false;
} else {
flag[temp] = true;
}
}
return true;
}
/**
* Extra Data Structure Solution
* unique --> Set
*/
public static boolean isUniqueChars2(String str){
if (str == null) {
return false;
}
Set<Character> set = new HashSet<Character>();
char[] arr = str.toCharArray();
for (int i = 0; i < str.length(); i++) {
if(set.contains(arr[i])) {
return false;
} else {
set.add(arr[i]);
}
}
return true;
}
/**
* brute force solution
* No extra data structure and space but time complexity increase
*/
public static boolean isUniqueChars3(String str) {
if (str == null) {
return false;
}
char[] arr = str.toCharArray();
for (int i=0; i<arr.length; i++) {
for (int j=i+1; j<arr.length; j++) {
if (arr[i] == arr[j]) {
return false;
}
}
}
return true;
}
}
@SethuVignesh
Copy link

The solution you have will work only for ASCII characters,
What about Strings which have 6000 unique characters.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment