SRM269 Div1 Level 1 PatternOptimizer

SRM269 Div1 Level 1 PatternOptimizer

少し古いですがSRM269から。私は結局Level3が簡単と誤認して０問解答＆チャレンジ失敗（-25)という最悪の結果に終わり、Div2へ転落しました。実はLevel1が気づけば簡単だったことを後で認識し、かなりショックを受けました・・・

問題

正規表現 ‘?’ （任意の１文字）、’*’（任意の０文字以上の文字）を使った文字列がある。これと同じ意味（例： “*??*a” = “?*?a”）を示す最短の文字列を返せ。同じ長さの回答がある場合は辞書順（* は ? より先）。

条件

• 文字列の長さは１～５０文字


• 文字列の文字は('a'-'z','A'-'Z')

考え方

まず、問題から特定文字列を最適化された文字列に置換していく問題である事を理解しなければならない。そのパターンは例題から見つかる。

"*??*a"　-> "*??a"
"*b**a*"　-> "*b*a*"
"cla??" 　-> "cla??"
"*?*?*?*"　-> "*???"
"T***nd?*"　-> "T*nd*?"

まず、連続する”*”は１つに省略できる。”?*”のペアは”*?”と同じ意味（１文字以上の任意の文字列）となるので、辞書順から”*?”にできる。これをパターン化すると”**”を”*”と置換、”?*”を”*?”と置換、の２つを可能な限り繰り返せばよい。

順に一度のsweepで実現するためには、置換によって文字列の長さが変わって文字列を調査するindexがずれる事を考慮する必要がある。私はここで色々なテストケースを用意したりして５分ほど不要な時間をとられた。”**”と”?*”が無くなるまでsweepを繰り返すと思えば、実はJavaならばStringクラスのreplaceAll(String reg, String replace)で置換すれば早い。この手の問題はこういった工夫で１分でも時間を短縮できるようがんばる。

解答例

public class PatternOptimizer{
 public String optimize(String pattern){
  // "**"と"?*"がなくなるまで置換を繰り返す
  while(pattern.indexOf("**") != -1  pattern.indexOf("?*")!=-1){
   pattern = pattern.replaceAll("\\*\\*","*");
   pattern = pattern.replaceAll("\\?\\*","*?");
  }
  return pattern;
 }
}