兄弟の単語を探します(2012.5.6百度実習)

テーマ:一つの単語の単語のアルファベット交換は、army->maryのような別の単語を得ることができ、兄弟の単語になります.辞書で兄弟を見つける単語を提供します.データ構造とクエリー・プロシージャについて説明します.
解法一:hash_を使うmapとチェーンテーブル(1)は、まず、兄弟の単語が同じkeyであり、兄弟の単語が異なるkeyではないようにkeyを定義する.たとえば、badのkeyがabd、goodのkeyがdgooのように、単語をアルファベットで小さいものから大きいものに並べ替えてkeyとします.(2)チェーンテーブルを使ってすべての兄弟の単語をつなぎ合わせ、hash_mapのkeyは単語のkey,valueはチェーンテーブルの開始アドレスである.(3)開始時には,まず辞書を巡回し,各単語をkeyに従って対応するチェーンテーブルに加える.(4)兄弟の単語を探す必要がある場合は、その単語のkeyを取ってhash_mapで対応するチェーンテーブルを見つければいいです.       hash_を作成しますmap時の時間複雑度はO(n)であり,兄弟単語を検索する際の時間複雑度はO(1)である.
解法2:hash_を同様に使用するmapとチェーンテーブル(1)は、アルファベットごとに1つの素数に対応し、対応する素数を乗算し、得られた値をhashすることで、兄弟単語の値は同じであり、異なる単語の素数の積は異なるに違いない.(2)チェーンテーブルを使ってすべての兄弟の単語をつなぎ合わせ、hash_mapのkeyは単語の素数積であり,valueはチェーンテーブルの開始アドレスである.(3)ユーザが入力した単語を計算し,hashを検索し,チェーンテーブルを遍歴して出力するとすべての兄弟単語が得られる.hash_を作成しますmap時の時間複雑度はO(n)であり,兄弟単語を検索する際の時間複雑度はO(1)である.
マス辞書ならB+ツリーで...
注:上記の2つの方法は比較的効率的なアルゴリズムであり、一般的な方法を紹介します.
解法3:全配列、そしてこの問題を順番に比較してみると、直感的には、入力された単語の全変換(単語の長さがnであれば、その全変換はn!個.同じアルファベットがあればn!ではない)を求め、単語の変換を求めて、変換ごとに辞書にあるかどうかを判断する.例えばabcを入力すると、その変換は3!=6種類:abc、acb、bca、bac、cab、cba.そしてこの6つの単語(もちろんここでは単語ではなく文字列)が辞書にあるかどうかを順番に判断し、辞書にあれば記録する.明らかにこのような思想の複雑度は比較的に高くて、nに対して少し大きいならば、n!恐ろしい増加過程であるため,この方法はあまり望ましくない.以下はフル配列コードです.

/**
     * @param src
     * @param start       
     * @param end        
     */
   public static void perm(String[] src,int start,int end){
        if(start==end){//                  ，          
            for(int i=0;i<=end;i++){
                System.out.print(src[i]);
            }
            System.out.println();
        }
        else{//       
            for(int i=start;i<=end;i++){
                String temp=src[start];//               
                src[start]=src[i];
                src[i]=temp;
                perm(src,start+1,end);//         
                temp=src[start];//         
                src[start]=src[i];
                src[i]=temp;
            }
        }
    }

辞書の「比較単語」の頭文字と同じ単語を取り出して配列に格納し、各組合せと辞書の単語を比較します.まず単語の長さを比較し、長さが同じであれば、比較を続けます.そうでなければ、次の単語を比較します.アルゴリズムは次のとおりです.

/**
     * @param src       
     * @param des       ，        ，         
     * @return
     */
    public static boolean compare(String src,String[] des){
        int len = src.length();
        if(len != des.length){//       ，        ，     
            return false;
        }
        int i = 1;//i  1          ，    
        while(i<len){
            if(des[i].equals(String.valueOf(src.charAt(i)))){
                i++;
                continue;
            }
            return false;
        }
        return true;
    }