TopCoder SRM215 Div2 500Pts

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

collectionからaddress[]の各要素の文字列が構成できないのは何ケースあるかを求めて返すメソッドを作成する。例えばcollection="AABC"で、address[]={"AC","BD","ACE","AAAC"}であれば、collectionに"A"じは二つしかなく"AAAC"は構成できない。また、"DE"はないので、2つの文字列"BD"、"ACE"も構成できず、3という値が返されることになる。なお、address[]は空白が含まれるが、それはcollection中にはなくても構成できないとはみなさない。

私の解答は以下の通り。

public class Mailbox {
 public int impossible(String collection, String[] address) {
  int isImpossible = 0;
  for( int i=0 ; i<address.length ; i++ ){
   String tmp = new String(collection); // collectionのコピー
   for( int j=0 ; j<address[i].length() ; j++ ){
    if( address[i].charAt(j) == ' ' ){
     continue; // 空白は無視
    }else{
     int pos = tmp.indexOf(address[i].substring(j,j+1));
     if( pos < 0 ){
      // indexOfが負の値ということはcollecionのコピーに文字がない
      isImpossible++;
      break;
     }else{
      // collectionのコピー変数から存在した文字を1つ削除する
      tmp = tmp.replaceFirst(address[i].substring(j,j+1), "");
     }
    }
   }
  }
  return isImpossible;
 }
}

得点は339.55/500。公式の平均点は378.67。細かいが、StringはStringBufferの方がよかったか。isImpossibleはnImpossibleの方がint型の数値を返すところからより妥当だということに気付いた。