Monday, February 18, 2013

[Cracking The Code Interview] 1-1


Description:
Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?

Thoughts: 
If we could use arrays, it is trivial to implement. Without additional data structures,  we could pick up a int variable and use bit manipulation to trace whether a character has shown up in the string before.

Code:
public static boolean IsUniqueChar(String s){ //Use an extra array 
boolean[] char_set = new boolean[256];
for(int i = 0; i < s.length(); i++){
int tmp = s.charAt(i);
if(char_set[tmp]){
return false;
}
char_set[tmp] = true;
}
return true;
}
public static boolean IsUniqueChar2(String s){ // Use bit manipulation
        int flag = 0;
for(int i = 0; i <s.length(); i++){
int tmp = s.charAt(i) - 'a';
if( (flag & (1<<tmp)) > 0 ){
return false;
}
flag = flag | (1<<tmp) ;
}
return true;
}

No comments:

Post a Comment