Pythonでバランスの取れた括弧を最大数のグループに分割するプログラム

問題概要

バランスの取れた括弧「(」と「)」だけで構成された文字列 s が与えられたとします。この文字列を、それ以上分割できない単位ごとに、できるだけ多くのバランスの取れたグループへと分割することを考えます。

たとえば、入力が "(()())()(())" の場合、出力は ['(()())', '()', '(())'] になります。それぞれのグループは、それ自体で完結したバランスの取れた括弧列となっています。

解法のアプローチ

この問題は、「現在読んでいる位置での括弧の深さ」を表すカウンタを1つ用意するだけで解くことができます。括弧の深さが 0 に戻った時点で、そこまでの部分文字列がひとつの完全なグループになるためです。

具体的な手順は次のとおりです。

• temp(作成中のグループ)を空文字列、groups(結果リスト)を空リスト、count(括弧の深さ)を 0 で初期化します。
• 文字列 s の各文字 b に対して、以下を繰り返します。
  • count が 0 かつ temp が空でない場合、直前のグループが完成しているので temp を groups に追加し、temp を空文字列にリセットします。
  • temp に b を連結します。
  • b が '(' なら count を 1 増やし、')' なら 1 減らします。
• ループ終了後、最後のグループとして temp を groups に追加します。
• groups を返します。

実装例(Python)

class Solution:
    def solve(self, s):
        temp = ''
        groups = []
        count = 0
        for b in s:
            if count == 0 and len(temp) > 0:
                groups.append(temp)
                temp = ''
            temp += b
            if b == '(':
                count += 1
            else:
                count -= 1
        groups.append(temp)
        return groups

s = "(()())()(())"
ob = Solution()
print(ob.solve(s))

入力

"(()())()(())"

出力

['(()())', '()', '(())']

処理の流れと計算量

入力 "(()())()(())" の場合、文字を左から順に走査すると、6 文字目で count が 0 に戻り、最初のグループ '(()())' が確定します。続いて 8 文字目で '()'、12 文字目で '(())' が確定し、最終的に 3 つのグループが得られます。

文字列を一度だけ走査すればよいため、時間計算量は O(n)、結果の格納に文字列長分の領域が必要なため空間計算量も O(n) です。括弧の対応関係をスタックで管理する必要がなく、カウンタ1つで済む点がこのアルゴリズムの大きな特徴です。