TopCoder SRM211 Div2 400Pts

今日のTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。

candidateに最も近い単語をdictionary[]から選び、その単語のインデックスを返すメソッドを作成する。単語の近さというのは、candidateとdictionary[i]の単語の文字を先頭から順番に比較したときに、一致した回数で定義する。candidateとdictionary[]の単語は長さはすべて同じであるものとする。また、登場する文字はa-zの小文字のアルファベットに限る。1文字もdictionary[]中に一致するものがなければ-1を返すようにせよ。マッチした回数が最大の単語が複数ある場合は、dictionary[]中で先に出てきた単語のインデックスを返すようにする。

私の解答は以下の通り。

public class grafixCorrupt {
 public int selectWord(String[] dictionary, String candidate) {
  boolean nomatch = true;
  int[] nmatch = new int[dictionary.length]; // 要素はすべて0で初期化される
  for( int i=0 ; i<dictionary.length ; i++ ){
   for( int j=0 ; j<dictionary[i].length() ; j++ ){
    // 単語中の文字が一致した回数をカウント
    if( dictionary[i].charAt(j) == candidate.charAt(j) ){
     nomatch = false; // 何度もfalseで上書きしているが問題ない
     nmatch[i]++;
    }
   }
  }
  if( nomatch ) return -1; // dictionary中の単語にcandidateが全く一致しない場合

  int max = -1;
  int idx = -1;
  // 前半のマッチした回数カウントから、もっともマッチした単語を調べる
  for( int i=0 ; i<nmatch.length ; i++ ){
   if( nmatch[i] > max ){ // 先に出てきた単語がidxに入るようにする
    max = nmatch[i];
    idx = i;
   }
  }
  return idx;
 }
}

得点は331.14/400、中央値は約213点。解答提出者のみに限った正解率は約91%。4回目のチャレンジで初めてLevel2の問題を解くことに成功した。