式内の括弧のバランスをO(1)空間・O(N²)時間計算量で判定するC++プログラム

概要

文字「(」「)」「{」「}」「[」「]」を含む文字列 str が与えられたとき、その括弧がバランスしているかどうかを判定するのが本記事のテーマです。

括弧が「バランスしている」とは、以下の条件を満たすことを指します。

• 開いた括弧は、必ず同じ種類の括弧で閉じられていること。
• 開いた括弧が、正しい順序で閉じられていること。

入力例1： str = "(()){}"
出力： Yes（バランスしている）

入力例2： str = "))(([]["
出力： No（バランスしていない）

アルゴリズムの考え方

一般的にこの種の問題はスタックを使えば O(N) 時間で解けますが、ここでは追加のメモリ領域 O(1) で解く手法を紹介します。その代わり、時間計算量は O(N²) になります。手順は以下のとおりです。

• 比較対象となる2つの括弧の位置を追跡するため、変数 a と b を用意します。
• カウンタ変数 count を管理します。開き括弧に遭遇したら +1、閉じ括弧に遭遇したら -1 します。
• 開き括弧に遭遇した場合は、b = a、a = a + 1、count = count + 1 と更新します。
• 閉じ括弧に遭遇した場合は count をデクリメントし、位置 a と b の括弧を比較します。
  • a と b の括弧が一致していれば、文字列の a 番目と b 番目の位置を「#」で置き換えます。その後、「#」以外の文字に到達するか b < 0 になるまで、a をインクリメント、b をデクリメントしていきます。
  • a と b の括弧が一致しなければ false を返します。
• 最後に count != 0 であれば false を返します。

C++実装例

// C++ implementation of the approach
#include <iostream>
using namespace std;
bool helperFunc(int& count1, string& s1, int& i1, int& j1, char tocom1){
    count1--;
    if (j1 > -1 && s1[j1] == tocom1) {
        s1[i1] = '#';
        s1[j1] = '#';
        while (j1 >= 0 && s1[j1] == '#')
            j1--;
        i1++;
        return 1;
    }
    else
        return 0;
}
bool isValid(string s1){
    if (s1.length() == 0)
        return true;
    else {
        int i1 = 0;
        int count1 = 0;
        int j1 = -1;
        bool result1;
        while (i1 < s1.length()) {
            switch (s1[i1]) {
                case '}':
                    result1 = helperFunc(count1, s1, i1, j1, '{');
                    if (result1 == 0) {
                        return false;
                    }
                break;
                case ')':
                    result1 = helperFunc(count1, s1, i1, j1, '(');
                    if (result1 == 0) {
                        return false;
                    }
                break;
                case ']':
                    result1 = helperFunc(count1, s1, i1, j1, '[');
                    if (result1 == 0) {
                        return false;
                    }
                break;
                default:
                    j1 = i1;
                    i1++;
                    count1++;
            }
        }
        if (count1 != 0)
            return false;
        return true;
    }
}
// Driver code
int main(){
    string str1 = "[[]][]()";
    if (isValid(str1))
        cout << "Yes";
    else
        cout << "No";
    return 0;
}

出力結果

Yes

計算量について

• 時間計算量：O(N²) ― 閉じ括弧ごとに、一致する開き括弧を探すために最大 N 文字さかのぼる可能性があるためです。
• 空間計算量：O(1) ― スタックなどの追加データ構造を使わず、入力文字列自体を書き換えて済ませているため、定数個の変数だけで処理できます。

メモリ使用量を最小限に抑えたい場合に有効なアプローチですが、速度を優先するならスタックを用いた O(N) の解法が一般的です。用途に応じて使い分けるとよいでしょう。