以下に、O(n^3) 時間、O(n^2) 空間の動的プログラミング ソリューションを C++ で示します。 しかし、このアルゴリズムを正当化するには、まず説明が必要です。以下では、連続していなければならない要素の順序付けられたサブセットを意味するために「サブストリング」を使用し、そうである必要のない順序付けられたサブセットを意味するために「サブシーケンス」を使用します。
有効であることがわかっている文字列を生成する
文字列の深さを、文字列に[含まれる の数から の数を引いたものと定義し]ます。
すべての有効な (「バランスの取れた」) ブラケット文字列が従わなければならないいくつかの規則を確立しましょう。
[との数は同じでなければなりません]。- 文字列の接頭辞が負の深さを持つことはありません。つまり、
]s よりも[s が多くなります。
これらは明らかに必要な条件です。文字列がいずれかの規則に違反している場合、その文字列は有効ではありません。しかし、有効であることがわかっている文字列を便利に生成できるようにするためには、これらの条件が十分であることを示す必要があります。つまり、これらの規則に従う文字列はすべて有効でなければならないということです。これを助けるために、補題を導入しましょう：
補題:空でない文字列が条件 (1) と (2) に従う場合、部分文字列として含まれている必要があります[]。
証明:で始まる必要があります。[そうしないと、長さ 1 のプレフィックスに]s よりも多くの s が含まれ[、(2) に違反するためです。したがって、少なくとも 1 つ]の が含まれている必要があります。そうしないと、i >= 1[と 0が存在]し、有効な文字列には (1) によってそれぞれが等しい数が含まれている必要があります。したがって、j > 1 のどこかの位置に a が最初に出現し、]その左側の文字が a でなければなりません[。
x条件 (1) と (2) に従う空でない文字列があるとします。レンマにより、それは を含まなければなりません[]。このペアを削除しても、これらの条件のいずれかに違反することはありません。そのため、結果の文字列が空でない場合でも、条件 (1) および (2) に従う必要があり、[]どこかに a が含まれている必要があります。[]したがって、空の文字列が残るまで s を削除し続けることができます。
有効な文字列の任意の位置に a を挿入する[]と、新しい有効な文字列が生成される必要があります。これは、新しいブラケットのペアが常に互いに一致し、他の一致したペアを妨害しないためです。x前の段落で s を削除したのと逆の順序で、空の文字列に s を繰り返し挿入することによって、元の文字列を作成できることに[]注意してください (これは自明です) x。条件 (1) および (2)) が有効です。
正しい再帰
OPの質問を表現する同等の方法は、「残りのサブシーケンスも有効になるように、文字位置の有効なサブシーケンスを選択できる方法はいくつありますか?」です。最初に次のように一般化すると、再帰を使用してこの問題を解決できます。
これまでに選択されたサブシーケンスの深さdが であり、これまでに選択されていないサブシーケンスの深さが であるとするとe、 position で始まる接尾辞から有効なサブシーケンスを選択しkて、残りのサブシーケンスも有効にする方法はいくつありますか?
この関数を呼び出しますcount(d, e, k)。元の質問に対する答えは今count(0, 0, 0)です。
実際、 は文字のd+e後の合計深度と等しくなければならないことに注意することで、問題をさらに単純化できます。kedkcount()
また、空のサブシーケンスを選択できるかどうかをテストするときは、d== 0であることをテストするだけで済みますe。if d== 0次に、元の文字列から正味の深さ 0 を差し引いています (深さ 0 で終了する必要があり、有効であると仮定して 0 を下回ってはなりません)。
これを再帰的に解決するには、考えられるすべてのサブシーケンスを検索するプロセスから最初の決定点を切り離す必要があります。長さ n の文字列のサブシーケンスは、次の n+1 ケースのいずれかに該当する必要があります: 空であるか、文字列内の n 文字のいずれかである左端の要素を持っています。この最初の決定を行った後、再帰によって生成されるサブシーケンスはすべて区別されます。
memo[][]再帰が適切に機能していれば、それをメモするのは簡単です。最初は -1 の値で埋められている 2D vector に特定の呼び出しの正しい答えを記録するだけです。関数count(d, k)には、長さ n の文字列に対してそれぞれ 0 から n/2 までと 0 から n までの範囲の 2 つのパラメーターがあるため、O(n^2) のスペースが必要であり、if (memo[d][k] == -1) {ブロックの内部はせいぜい実行されます。 O(n^2) 回。これが発生するたびに、O(n) ループが実行され、時間の複雑さが O(n^3) になります。
実際のコード
#include <iostream>
#include <vector>
#include <string>
using namespace std;
class PartitionCounter {
// Return the number of subsequences of the suffix of v beginning at position k
// that are (a) valid, given that the initial depth of the subsequence is d (on
// account of it being the suffix of some larger subsequence), and (b)
// leave behind a remainder subsequence that is also valid, given that
// the remainder sequence has initial depth depths[k]-d.
int count(int d, int k) {
// If a prefix of either sequence (selected or remaining) has more ']'s
// than '['s then there can't be any completing subsequences.
if (d < 0 || depths[k] - d < 0) {
return 0;
}
// Only compute the answer if we haven't already.
if (memo[d][k] == -1) {
// A subsequence must either contain no elements, or a leftmost element
// at some position. All subsequences produced by recursion after this
// initial choice are distinct (when considering the sequence of
// character indices included, though not necessarily when considering
// the sequence of characters themselves).
// Try including no elements. This effectively terminates the larger
// subsequence that the selected subsequence is part of, so it can be
// legal only if its depth is 0. It also effectively includes all
// remaining characters in the remainder sequence, but if the selected
// subsequence has depth 0 and the original string does too, then it's
// implied that the remainder must also have total depth 0, so we don't
// need to check it.
int n = (d == 0);
// Try including a leftmost element at each remaining position.
// If this would cause a remainder subsequence that has negative
// depth, stop: any later loop iterations would also create illegal
// remainder subsequences.
for (int i = k; i < v.size() && depths[i] - d >= 0; ++i) {
n += count(d + v[i], i + 1);
}
memo[d][k] = n;
}
return memo[d][k];
}
vector<int> v; // 1 for '[', -1 for ']'
vector<int> depths; // depths[i] is the sum of the 1st i elements
vector<vector<int> > memo; // DP matrix. -1 => not computed yet
public:
PartitionCounter(string s) : memo(s.size() / 2 + 1, vector<int>(s.size() + 1, -1)) {
depths.push_back(0);
int total = 0;
for (int i = 0; i < s.size(); ++i) {
v.push_back(1 - 2 * (s[i] == ']')); // Map '[' to 1 and ']' to -1
depths.push_back(total += v[i]);
}
}
int count() {
if (depths.back() == 0) {
return count(0, 0);
} else {
return 0; // Need to handle invalid strings specially
}
}
};
int main(int argc, char **argv) {
PartitionCounter c(argv[1]);
cout << c.count() << '\n';
}
結果
C:\>partitioncounter []
2
C:\>partitioncounter [[]]
6
C:\>partitioncounter [[[]]]
20
C:\>partitioncounter [[[[]]]]
70
C:\>stopwatch partitioncounter [][[[[[][][][][[][][]]]]]][]
10001208
stopwatch: Terminated. Elapsed time: 15ms
stopwatch: Process completed with exit code 0.
C:\>stopwatch partitioncounter [][[[[[][[[]][][][[]]][[][]]]]]][]
562547776
stopwatch: Terminated. Elapsed time: 0ms
stopwatch: Process completed with exit code 0.
もちろん、余分なビットが必要な場合のlong long代わりに、または何でも使用できます。int
編集: ishi によって指摘されたバグを修正しました。選択したサブシーケンスから除外する文字をスキップすると、残りのサブシーケンスにそれらが蓄積されます。]これまでのところ、サブシーケンス全体でs よりも多くの sを持つ残りのサブシーケンスのみを効果的に除外していましたが、条件 (2) に違反しないようにするために、これがすべてのプレフィックスに[当てはまることを確認する必要があります。ストリング。ループを早期に停止することでこれを行うため、これらの違反する残りのサブシーケンスが最初から生成されることはありません。おまけとして、アルゴリズムが高速になります! :)
