データ構造 〜 第1章 配列と文字列 問題1-1

世界で闘うプログラミング力を鍛える150問 ~トップIT企業のプログラマになるための本~

問題1-1を解いた。
ある文字列がユニーク（重複する文字がない）かどうかを判定するアルゴリズムの実装。

まず最初に、単純な全探索のプログラム。第1感で思いついたのがこれだから、現在の私の実力はそんなもの・・・。
文字列がn文字からなる場合、計算量はn**2のオーダー。

public class Solve1_1 {
	public static void main(String args[]){
		Solve1_1 solve = new Solve1_1();
		boolean isUnique = solve.isUnique("abcdde");
		
		if(isUnique){
			System.out.println("String is Unique.");
		}else{
			System.out.println("String is Not Unique.");
		}
	}
	
	/**
	 * ユニークならtrueを返す。
	 * @param word 分析対象の文字列。
	 * @return boolean
	 */
	public boolean isUnique(String word){
		int wordLength = word.length();
		for(int i=0; i<wordLength; ++i){
			Character character = word.charAt(i);
			for(int j=0; j<wordLength; ++j){
				if(j!=i){
					if(character == word.charAt(j)){
						return false;
					}
				}
			}
		}
		return true;
	}
}

文字列がASCHIIだとすると、文字種類は256個に限定でき、それ故、次の解答のような最適化も考えられることが紹介されていた。
言われれば、「なるほど！」と思うが、発想になかった。ボクにっぽん人だからね！
それはそうとして、使用済みかどうかを、配列をハッシュテーブルとして使用する点はどこでも使えるポイント。

public class Solve1_1 {
	public static void main(String args[]){
		Solve1_1 solve = new Solve1_1();
		//boolean isUnique = solve.isUnique("aあい");
		boolean isUnique = solve.isUnique2("ab");
		
		if(isUnique){
			System.out.println("String is Unique.");
		}else{
			System.out.println("String is Not Unique.");
		}
	}
	
	/**
	 * ユニークならtrueを返す。
	 * @param word 分析対象の文字列。
	 * @return boolean
	 */
	public boolean isUnique2(String word){
		//文字種類の数に制限があることを利用した最適化
		if(word.length() > 256){
			//鳩ノ巣原理から重複する文字があることは自明
			return false;
		}
		
		boolean[] char_set = new boolean[256];
		
                //既に使用したかどうかは、配列をハッシュテーブルのように扱うところがポイント
		for(int i=0; i<word.length(); ++i){
			int val = word.charAt(i);
			if(char_set[val]){
				return false;
			}else{
				char_set[val] = true;
			}
		}
		return true;
	}
}