SRM628Div2Medium
問題
長さNの文字列が与えられる。文字列の要素は(,),{,},[,]の6文字かどの文字にもなれる'X'のどれかである。全ての括弧が対応しているかを確認せよ。ある括弧をまたいで対応している場合は、無効とする。(例: ([)])
解法
ひとつのスタックを用いることで、対応しているかどうかの確認はできる。
Xの数は最大でも5個しか含まれないので全探索をする。
計算量
対応確認:O(N)
Xの探索:
全体:
長さNの文字列が与えられる。文字列の要素は(,),{,},[,]の6文字かどの文字にもなれる'X'のどれかである。全ての括弧が対応しているかを確認せよ。ある括弧をまたいで対応している場合は、無効とする。(例: ([)])
ひとつのスタックを用いることで、対応しているかどうかの確認はできる。
Xの数は最大でも5個しか含まれないので全探索をする。
対応確認:O(N)
Xの探索:
全体: