TopCoder SRM402 Div2 250Pts

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

words[]という1つの要素が1つの単語からなる文字列型配列が与えられる。i番目の要素がi番目の単語を省略したものを返せ。単語の省略したものというのは、他の単語の接頭辞にならない、かつ空文字ではないという条件を満たす、もっとも短い接頭辞である。この制約により、すべての与えられた単語の省略した形があるということが保証される。

私の解答はこちら。

public class WordAbbreviation {

 public String[] getAbbreviations(String[] words) {
  String[] ret = new String[words.length];
  StringBuffer sb = new StringBuffer();
  for( int i=0 ; i<words.length ; i++ ){ // 各単語について
   for( int j=0 ; j<words[i].length() ; j++ ){ // 先頭からj番目の文字まででユニークか判定
    sb.append(words[i].charAt(j)); // 1文字増やす
    boolean isUnique = true;
    String tmp = sb.toString();
    for( int k=0 ; k<words.length ; k++ ){
     if( i==k ) continue;
     if( words[k].startsWith(tmp) ){ // 接頭辞で単語の特定ができない場合
      isUnique = false;
      break;
     }
    }
    if( isUnique ){
     ret[i] = tmp;
     break;
    }
   }
   sb.delete(0, sb.length());
  }
  return ret;
 }

}

得点は225.45/250、1回のsubmitでシステムテストクリア。中央値は約158点。