2012年2月21日火曜日

TopCoder SRM335 Div2 250Pts

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

回文というのは、右から読んでも左から読んでも同じになるものである。sという文字列が与えられたとき、sの右に0文字以上の文字を最小限足すことで得られる、もっとも短い回文を返せ。これは唯一に定められる。

私の解答はこちら。

public class Palindromize {

 public String minAdds(String s) {
  StringBuffer sb = new StringBuffer(s); // 文字列の反転にStringBuffer
  String rev = sb.reverse().toString();
  int idx = 0;
  int len = s.length();
  for( int i=0 ; i<len ; i++ ){
   String s1 = s.substring(i);
   String s2 = rev.substring(0, len-i);
   System.out.println("---");
   System.out.println(s1);
   System.out.println(s2);
   if( s1.equals(s2) ){
    return s + rev.substring(len-i);
   }
  }
  return null;
 }

}

得点は177.51/250、中央値は約164点。元の文字列の後ろn文字ととひっくり返した文字列の先頭n文字をnが小さくなる方向に探索していけばよいというだけなのだが、それに気付くのに思いのほか手間取った。

0 件のコメント:

コメントを投稿

フォロワー

ページビューの合計