TopCoder SRM308 Div2 450Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。問題文について説明する。

ハフマン符号を使ってテキストをエンコーディングするとき、各文字は0-1のビット表現された文字に置き換えられる。この置き換えはシンボルのビット文字列表現は決して他のシンボルのビット文字列表現の接頭辞にはならない(要は各0-1は1つの文字を表すためにしか利用されないということだ)。この性質によりエンコードされたテキストをデコードする際のあいまいさはなくなる。

問題ではarchiveとdictionary[]という文字列と文字列型配列が与えられる。dictionaryのi番目の要素はアルファベットのi番目の大文字のビット文字列表現である。archiveをdictionary[]を用いてデコードし、その結果を文字列として返すメソッドを作成せよ。

私の解答はこちら。

public class HuffmanDecoding {

 public String decode(String archive, String[] dictionary) {
  int aPos = 0; // デコードしている文字の現在位置
  StringBuffer ret = new StringBuffer();
  while( true ){
   if( aPos >= archive.length() ) break; // 最後まで見たら終了
   StringBuffer sb = new StringBuffer();
   for( int i=aPos ; i<archive.length() ; i++ ){
    sb.append(archive.charAt(i)); // archiveから1文字追加
    int nMatch = 0;
    int idx = 0;
    String comp = sb.toString();
    for( int j=0 ; j<dictionary.length ; j++ ){
     if( comp.equals(dictionary[j]) ){
      nMatch++; // dictionaryで一致した文字の数をカウント
      idx = j; // dicrionaryの何番目と一致したかを記録
     }
    }
    if( nMatch == 1){ // デコードできる文字が1つに定まったら
     char c = (char)(idx + 'A'); // キャストに注意
     ret.append(c); // 文字を解答に追加
     aPos = i+1; // 次の文字から続けて見ていく
     break;
    }
   }
  }
  return ret.toString();
 }

}

得点は379.88/450、中央値は約223点。らしからぬ1発submitでした。問題を解く方針としては、archiveの注目している位置から1文字ずつ追加していき、dictionaryと比較して、候補になる文字が一つに絞られた瞬間にデコードして一つの文字に置き換えるということを実装するものです。