Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
【解答】1.1 ある文字列が、すべてユニークである(重複する文字がない)かどうかを判定するアルゴリズムを実装してください。また、それを実装するのに新たなデータ構造が使えない場合、どのようにすればよいですか?
// 入力は小文字のアルファベットのみと仮定すると、
// 26種類('a'~'z')の文字の有無を4byteのビットベクトル([0,0,0,0,...])で表現できる。
// 'a' => dec:97 bin:1100001 'a'-'a':0
// 'b' => dec:98 bin:1100010 'b'-'a':1
// 'c' => dec:99 bin:1100011 'c'-'a':2
// 'd' => dec:100 bin:1100100 'd'-'a':3
// ...
public class IsUniqueAlphabets {
public static void main(String[] args) {
boolean flg = isUniqueAlphabets("abcd");
System.out.print("every alphabet is unique: " + flg);
}
public static boolean isUniqueAlphabets(String str){
if(str.length() > 26) return false;
int checker = 0;
for(int i = 0; i < str.length(); i++){
int val = str.charAt(i) - 'a';
if((checker & (1 << val)) > 0) {
return false;
}
checker |= 1 << val;
}
return true;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment