読者です 読者をやめる 読者になる 読者になる

SRM 521 Div2 Medium MissingParentheses

問題

()からなる文字列sは以下の条件でwell formedと呼ばれる

  • 空文字列はwell formed
  • sがwell formedなら(s)もwell formed
  • s, tがwell formedならstもwell formed

与えられた文字列をwell formedにする時挿入する最小の文字数を答えよ.

解答

入力文字列から,部分文字列の中で最小のwell formedから順に消去していく.
# "(空文字列)"から消していく
そうすると((((((か))))))の連続となるはずなので(逆のカッコを挿入するとwell formedなら部分文字列が必ず作れるため),そこからwell formedを作ろうとすると残った文字列の長さ分だけのカッコを挿入する必用がある.

#他人のコードを読んで,'('の数と')'の差分を答えればよかったことに気づいた.こちらのほうがシンプル

class MissingParentheses
{
public:
  int countCorrections(string par)
    {
      bool notend = true;
      while(notend){
        int n = par.size();
        notend = false;
        for(int i = 1; i < n; i++){
          if (par[i-1]=='(' && par[i] == ')'){
            notend = true;
            par = par.substr(0, i-1) + par.substr(i+1);
            break;
          }
        }
      }
      return par.size();
    }
};