2012年9月24日月曜日

TopCoder SRM428 Div2 250Pts

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

ジョンとブラスは文字列の理論について大学で学んでいる。ブラスはパリンドローム(訳注:回文のこと)が大好きである。パリンドロームというのは前からも後ろからも同じように読める単語のことである。ジョンはsという文字列を受け取った時に、0文字以上の文字をsの後ろにつけてパリンドロームを作ることで、ブラスを驚かせたいと思っている。ジョンはパリンドロームはできるだけ短くしたいと考えている。sという文字列が与えられたとき、ジョンが生成できるもっとも短いパリンドロームの文字列の長さを返すメソッドを作成せよ。

私の解答はこちら。

public class ThePalindrome {

 public int find(String s) {
  StringBuilder sb = new StringBuilder(s);
  String rev = sb.reverse().toString(); // sをひっくり返した単語
  for( int i=0 ; i<s.length() ; i++ ){
   String s1 = s.substring(i, s.length()); // sの先頭i文字目以降と
   String s2 = rev.substring(0, rev.length()-i); // ひっくり返した文字列の最後の方を比較して
   if( s1.equals(s2) ) return s.length() + i; // 一致したときの最短パリンドロームの長さを返す
  }
  return s.length()*2-1;
 }

}

得点は243.03/250、1回のsubmitでシステムテストクリア。ひっくり返した文字列との比較の方法がポイント。

0 件のコメント:

コメントを投稿

フォロワー

ページビューの合計