cc150_1.1

1.1 Implement an algorithm to determine if a string has all unique characters. What if
you cannot use additional data structures?
//if it's ASCII characters: 256 candidates
public boolean isUnique(String str){
  if(str.length() > 256) return false;
  boolean[] v = new boolean[256];
  for(int i = 0; i < str.length(); i++){
      int ch = str.charAt[i];
      if(v[ch]) return false;
      v[ch] = true;
  }
  return true;
}

//use bit to save space: assume that it's a~z characters: 26 candidates, so one int = 32 bits is enough.
public boolean isUnique(String str){
  int checker = 0;
  for(int i = 0; i < str.length(); i++){
    int ch = str.charAt[i] - 'a';
    if( (checker & (1<<ch)) ) return false;
    checker |= (1<<ch);
  }
  return true;
}