PythonでO(1)空間・O(N²)時間計算量によるバランスの取れた括弧の判定方法

文字列 str に括弧「(」「)」「{」「}」「[」「]」が含まれているとします。このとき、これらの括弧がバランスしているかどうかを判定する必要があります。括弧がバランスしているとは、開き括弧と閉じ括弧が同じ種類で正しく対応しており、正しい順序で閉じられている状態を指します。

例えば、入力が {([])} の場合、出力は True になります。

解法のアプローチ

この問題を解くために、以下の手順に従います。

• カウンタ cnt を 0、インデックス i を 0、j を -1 で初期化します
• 関数 solve() を定義します。引数として s と temp を受け取ります
• solve() 内では cnt をデクリメントし、s をリストに変換します
• j > -1 かつ s[j] が temp と一致する場合：
  • s[i] と s[j] を '#' でマークします
  • j が 0 以上で s[j] が '#' の間、j をデクリメントし続けます
  • i をインクリメントして 1 を返します
• それ以外の場合は 0 を返します
• メイン処理では以下を実行します：
  • s の長さが 0 の場合は True を返します
  • そうでなければ ans を False で初期化し、i が s の長さ未満である間ループします
    • s[i] が '}' なら solve(s, '{') を呼び出し、結果が 0 なら False を返します
    • s[i] が ')' なら solve(s, '(') を呼び出し、結果が 0 なら False を返します
    • s[i] が ']' なら solve(s, '[') を呼び出し、結果が 0 なら False を返します
    • それ以外の場合は j = i とし、i をインクリメント、cnt をインクリメントします
  • ループ終了後、cnt が 0 でなければ False を返します
  • 最後に True を返します

実装例

理解を深めるために、以下の実装を見てみましょう。

cnt = 0
i = 0
j = -1

def solve(s, temp):
    global i, j, cnt
    cnt -= 1
    s = list(s)
    if j > -1 and s[j] == temp:
        s[i] = '#'
        s[j] = '#'
        while j >= 0 and s[j] == '#':
            j -= 1
        i += 1
        return 1
    else:
        return 0

def bracketOrderCheck(s):
    global i, j, cnt
    if len(s) == 0:
        return True
    else:
        ans = False
        while i < len(s):
            if s[i] == '}':
                ans = solve(s, '{')
                if ans == 0:
                    return False
            elif s[i] == ')':
                ans = solve(s, '(')
                if ans == 0:
                    return False
            elif s[i] == ']':
                ans = solve(s, '[')
                if ans == 0:
                    return False
            else:
                j = i
                i += 1
                cnt += 1
        if cnt != 0:
            return False
        return True

print(bracketOrderCheck("{([])}"))

入力

"{(()[])}"

出力

True

計算量について

このアルゴリズムはスタックなどの追加データ構造を使用せず、既存の変数だけで処理を行うため、空間計算量は O(1) となります。一方、閉じ括弧を見つけるたびに対応する開き括弧を文字列内で遡って探索する必要があるため、最悪の場合の時間計算量は O(N²) になります。一般的なスタックベースの手法では O(N) の追加メモリが必要ですが、この方法ではメモリ使用量を最小限に抑えられる点が特徴です。