文字列を「正しい」ものにするために、括弧の文字列の部分文字列にあるすべての括弧を反転する操作が何回必要ですか?

cs.stackexchange https://cs.stackexchange.com/questions/119847

  •  28-09-2020
  •  | 
  •  

質問

すべての開始括弧の後ろのどこかに対応する閉じ括弧があり、すべての閉じ括弧の前のどこかに対応する開始括弧がある場合、括弧の文字列を「正しい」と呼びます。例えば

(())()((()()))

は正しい文字列であり、

)()()(

は正しくない文字列です。

操作は、入力文字列の連続したサブシーケンスを取得し、そのサブシーケンス内のすべての括弧を「反転」することで構成されます。

任意の括弧文字列 (偶数長さ) が与えられた場合、そのタスクは、それを「正しい」括弧文字列に変更するために必要なそのような操作の最小数を見つけることです。

この問題を考察する別の方法は、+1 と -1 の文字列を用意し、この文字列のすべてのプレフィックスを非負にするために必要な演算 (一定間隔のすべての数値に -1 を掛ける) の最小数を見つけようとすることです。すべての接尾辞は非正です。

役に立ちましたか？

解決

Yuval映画違いのコメントで提案されている $ \ mathcal {O}（n ^ {2}）$ の問題を解決することができます。 DP。

最初に間隔が重ならないと仮定することができることに注意してください。任意の2つの重複区間 $ [a、b）$ と $ [c、d）$ です。 wlog $ A \ LEQ C $ 。次に、2つの間隔を間隔で置き換えることができます $ [A、C）$ 、 $ [\ min（b、d） ）、重ならない\ max（b、d））$ は、全長が短く、全く同じ要素をカバーしています。

オープニングブラケットを $ 1 $ で置き換え、 $ - 1 $ を含む括弧を閉じます。ここで、問題は、すべての接頭辞が非負の合計を持つように、最小操作数「」を適用し、配列全体の合計はゼロ;

左から右に解決されます。すべての位置で、間隔を開始するか、アクティブな間隔を終了することができます。

let $ dp [m] [s] [0] $ は、最初の $ m $ 要素は非負、最初の $ m $ 要素の合計は $ s $ 、そして私たちはアクティブな間隔はありません。同様に $ dp [m] [s] [1] $ は、アクティブな間隔があるのと同じ値です。

$ m $ th値が $ 0 \ leq s \ leq m $ 設定

  • $ dp [m] [0]= dp [m-1] [S-1] [0] [0] $
  • $ dp [m] [1]= DP [M-1] [S + 1] [1] [1] $

それ以外の場合は

を設定します

  • $ dp [m] [0]= DP [M-1] [S + 1] [0] [0] $
  • $ dp [m] [s] [1]= DP [M-1] [S-1] [1] [1] $ 。

その後終了して間隔を開始する、設定

  • $ dp [m] [0]=min（dp [m] [0]、dp [m] [1]） $
  • $ dp [m] [1]=min（dp [m] [s] [1]、dp [m] [0] + 1）$

基本ケースは $ dp [0] [0] [0]= 0 $ 、 $ dp [0 ] [0] [1]= 1 $ 。

$ \ mathcal {O}（n ^ {2}）$ 状態、 $ \ \ \ \ \ Mathcal {O}（1）$ それぞれを計算するための作業、したがって、アルゴリズムは $ \ mathcal {O}（n ^ {2}）$ 。 DPは、 $ \ mathcal {o}（n）$ メモリを使用して、 $ dpの値を格納することによって実装できます。現在の $ m $ の$ 。

これはアルゴリズムのC ++実装です。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    string str;
    cin >> str;
    int n = str.size();

    vector<int> dp0 = {0}, dp1 = {1};
    for (int m = 1; m <= n; ++m) {
        vector<int> nxt0(m + 1, n + 1), nxt1(m + 1, n + 1);
        for (int i = 0; i < m; ++i) {
            if (str[m-1] == '(') {
                nxt0[i+1] = dp0[i];
                if (i > 0) nxt1[i-1] = dp1[i];
            } else {
                nxt1[i+1] = dp1[i]);
                if (i > 0) nxt0[i-1] = dp0[i];
            }
        }
        dp0 = nxt0;
        dp1 = nxt1;
        for (int i = 0; i <= m; ++i) dp1[i] = min(dp1[i], dp0[i] + 1); // Start interval
        for (int i = 0; i <= m; ++i) dp0[i] = min(dp0[i], dp1[i]); // Stop interval
    }
    cout << dp0[0] << '\n';
}
.

他のヒント

いい質問ですね！

ここで、より一般的な用語で問題を説明します。

バランスの取れた括弧

部分文字列「()」を繰り返し削除して空の文字列に変更できれば、括弧の文字列のバランスが取れています。たとえば、空の文字列「()」と「(())()((()()))」はバランスが取れていますが、「())」と「)()()(」はバランスが取れていません。

バランスの取れた文字列は「(」で始まり「)」で終わる必要があることは明らかです。長さも均等でなければなりません。

弦のバランスをとるための最小操作の問題

させて s 空でない長さの括弧の文字列であること n. 。実行できる唯一の操作は、部分文字列内のすべての括弧を反転することです。つまり、文字列内のいくつかの連続文字について、すべての "(" を ")" に、すべての ")" を "(" に変更します。問題は、次のような最小の操作数を見つける方法です。 s バランスのとれた。

動的計画法によるアプローチ

適切な副問題は何ですか?彼らです dp[i][j] のために 0 <= i < j < n, 、 どこ dp[i][j] インデックス間の部分文字列のバランスをとる演算の最小数です。 i とインデックス j 包括的な。バランスをとるために必要な操作の最小数 s は dp[0][n-1].

奇数の長さの文字列はバランスが取れないため、今後は偶数の長さの文字列に限定して説明します。

基本的なケース dp[i][i+1] 間の部分文字列の場合は 0 です。 i そして i+1 バランスが取れている、つまり「()」。それ以外の場合は 1 です。

再発関係Java を使用して漸化関係を定義します。

void dp(int i, int j) {
    assert 0 <=i && i + 2 < j && j <= L;

    int min = dp[i + 1][j - 1];
    if (s.charAt(i) == ')' && s.charAt(i + 1) == '(') min++;
    if (s.charAt(j) == '(' && s.charAt(j - 1) == ')') min++;

    for (int k = i + 1; k < j - 1; k+=2) {
        if (a[k] == 1 && a[k + 1] == -1) {
            if (min > dp[i][k] + dp[k + 1][j] - 1) {
                min = dp[i][k] + dp[k + 1][j] - 1;
            }
        } else {
            if (min > dp[i][k] + dp[k + 1][j]) {
                min = dp[i][k] + dp[k + 1][j];
            }
        }
    }

    dp[i][j] = min;
}

漸化関係は、バランスの取れた文字列の次のよく知られた特性から得られます。空ではない文字列は、2 つのバランスのとれた文字列、または「(」の後にバランスのとれた文字列と「)」が続いた場合にのみバランスがとられます。

その前の処理は、 for を設定するループ min することが dp[i + 1][j - 1] プラス 0、1、または 2 は、「(」の後にバランスのとれた文字列が続き、さらに「)」がバランスのとれた文字列でなければならないという事実から来ています。

での処理は、 for 縮小しようとするループ min に dp[i][k] + dp[k + 1][j] 人によってはマイナス0か1 k それはその間にあります i そして j, 、2つのバランス弦の連結はバランス弦でなければならないという事実に由来しています。

このアプローチの時間計算量は次のとおりです。 $O(n^3)$. 。空間の複雑さは、 $O(n^2)$.

「最もアンバランスな」弦の長さ

2 回未満の操作ではバランスをとれない文字列の最小の長さは 4 です。例えば、 "）（（（"

3 回未満の操作でバランスをとることができない文字列の最小の長さは 10 です。例えば、 "）（（（（（（））（"

4 回未満の操作でバランスをとることができない文字列の最小の長さは 22 です。例えば、 "）（（））））（（（（（（（（（（（（））（"。

質問：少なくとも 5 回の操作を必要とする文字列の最小の長さはどれくらいですか?計算したところ、28 より大きくなければなりません。ただし、私の計算では実際の値を決定するには十分ではありません。これらの最小の長さをどれくらい速く計算できるでしょうか?

ライセンス： CC-BY-SA と 帰属
所属していません cs.stackexchange
scroll top