Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
【解答】1.1 ある文字列が、すべてユニークである(重複する文字がない)かどうかを判定するアルゴリズムを実装してください。また、それを実装するのに新たなデータ構造が使えない場合、どのようにすればよいですか?
// 仮に文字種類が256種類として、サイズが256の配列を作り、
// 1文字の文字コードをインデックスとして、配列にtrue/falseを入れる。
// 時間計算量は文字列の長さをnとして O(n)
// 空間計算量は文字列の長さに関係なく O(1)
// boolean[] char_set と int i,len,val がメモリを使用する。
public class IsUniqueChar {
public static void main(String[] args){
boolean flg = isUniqueChar(args[0]);
System.out.print("every character is unique: " + flg);
System.out.print("\n");
}
public static boolean isUniqueChar(String word){
// 文字種類が256の時、文字列の長さが256文字より大きければ、必ず重複がある。
if (word.length() > 256) return false;
// サイズ256の配列を定義する。
boolean[] char_set = new boolean[256];
int len = word.length();
for(int i = 0; i < len; i++){
// 引数wordから、一文字取りint valに代入する。
// 'a' は10進数で 97 になる。
// 'b' は10進数で 98 になる。
int val = word.charAt(i);
if(char_set[val]){
return false;
}
char_set[val] = true;
}
return true;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment