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;
}
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment