Promble:

Implement an algorithm to determine if a string has all unique characters. What if you cannot use addtional data structure?

My solution:

1.ckeck wether the length of str is really equal to 0 or more than 256, if yes, it will return false

2. ASCII have 256 character

3 . use ToArray function chage string as char array

4. sort char array

5. compare between two character, get duplicate or not

code: 

public static boolean different(String str){

if(str.length()==0||str==null||str.length()>256) return false;

char[] strlist = str.toCharArray();

Arrays.sort(strlist);

for(int i= 1; i<strlist.length; i++){

if(strlist[i]==strlist[i-1])

return true;

}

return false;

}

 

The given solution:

1. build a boolean Array and record the character appear on the string according the ASCII value 

2. if corresponding ASCII value is exist, then return false.

code:

public static boolean isUniqueChars2(String str){

if(str.length()==0||str.length()>256) return false;

boolean[] char_set = new boolean[256];

for(int i =0 ; i < str.length();i++){

int value = str.charAt(i)

if(char_set[value]){

return false;

}

char_set[value]=true;

}

return true;

}