Let us define a regular brackets sequence in the following way:
1. Empty sequence is a regular sequence.
2. If S is a regular sequence, then (S) and [S] are both regular sequences.
3. If A and B are regular sequences, then AB is a regular sequence.
For example, all of the following sequences of characters are regular brackets sequences:
(), [], (()), ([]), ()[], ()[()]
And all of the following character sequences are not:
(, [, ), )(, ([)], ([(]
Some sequence of characters '(', ')', '[', and ']' is given. You are to find the shortest possible regular brackets sequence, that contains the given character sequence as a subsequence. Here, a string a1 a2 ... an is called a subsequence of the string b1 b2 ... bm, if there exist such indices 1 = i1 < i2 < ... < in = m, that aj = bij for all 1 = j = n.
思路和POJ 2955是类似的。我们用DP[i][j]表示把子串s[i, j]补完成合法序列所需要的最少的字符数。我们有递推公式:
- DP[i][j] = D[i + 1][j],如果s[i]在s[i + 1, j]中没有括号与之match
- DP[i][j] = max(dp[i + 1][k - 1] + dp[k + 1][j]),如果s[i]和s[k]match
但是这个公式只能算出最少需要补完多少个字符来使之合法。我们还需要记录打印结果的路径(只打印满足条件的一个即可),我们用path[i][j]来记录s[i,j]的分割点,如果s[i]没有match,path[i][j] = -1;如果s[i]和s[k]match且其使得需要补完的char数最少,path[i][j] = k。我们打印的时候根据path自上而下递归地打印即可,详细可以参见代码中的print方法。时间复杂度空间复杂度均为O(n^2),代码如下:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//POJ 1141 | |
/* | |
Let us define a regular brackets sequence in the following way: | |
1. Empty sequence is a regular sequence. | |
2. If S is a regular sequence, then (S) and [S] are both regular sequences. | |
3. If A and B are regular sequences, then AB is a regular sequence. | |
For example, all of the following sequences of characters are regular brackets sequences: | |
(), [], (()), ([]), ()[], ()[()] | |
And all of the following character sequences are not: | |
(, [, ), )(, ([)], ([(] | |
Some sequence of characters '(', ')', '[', and ']' is given. You are to find the shortest possible regular brackets sequence, that contains the given character sequence as a subsequence. Here, a string a1 a2 ... an is called a subsequence of the string b1 b2 ... bm, if there exist such indices 1 = i1 < i2 < ... < in = m, that aj = bij for all 1 = j = n. | |
Input: | |
The input file contains at most 100 brackets (characters '(', ')', '[' and ']') that are situated on a single line without any other characters among them. | |
Output: | |
Write to the output file a single line that contains some regular brackets sequence that has the minimal possible length and contains the given sequence as a subsequence. | |
*/ | |
#include <cstdio> | |
#include <cstring> | |
const int MAX = 105; | |
int dp[MAX][MAX], path[MAX][MAX]; | |
char s[MAX]; | |
void print(int i, int j) | |
{ | |
if(i > j)return; | |
if(i == j) | |
{ | |
if(s[i] == '(' || s[i] == ')')printf("()"); | |
else printf("[]"); | |
return; | |
} | |
if(path[i][j] == -1) | |
{ | |
print(i, i); | |
print(i + 1, j); | |
} | |
else | |
{ | |
int k = path[i][j]; | |
printf("%c", s[i]); | |
print(i + 1, k - 1); | |
if(s[i] == '(')printf(")"); | |
else printf("]"); | |
print(k + 1, j); | |
} | |
} | |
int main() | |
{ | |
while(gets(s)) | |
{ | |
int len = strlen(s); | |
if(len == 0) | |
{ | |
printf("\n"); | |
continue; | |
} | |
memset(dp, 0, sizeof(dp[0][0] * MAX * MAX)); | |
memset(path, 0, sizeof(path[0][0] * MAX * MAX)); | |
for(int i = 0; i < len; ++i)dp[i][i] = 1; | |
for(int j = 0; j < len; ++j) | |
{ | |
for(int i = j - 1; i >= 0; --i) | |
{ | |
//assume s[i] doesn't match | |
dp[i][j] = dp[i + 1][j] + 1; | |
path[i][j] = -1; | |
for(int k = i + 1; k <= j; ++k) | |
{ | |
if(s[i] == '(' && s[k] == ')' || s[i] == '[' && s[k] == ']') | |
{ | |
int cost = dp[i + 1][k - 1] + dp[k + 1][j]; | |
if(cost < dp[i][j]) | |
{ | |
dp[i][j] = cost; | |
path[i][j] = k;//s[k] matches s[i] | |
} | |
} | |
} | |
} | |
} | |
print(0, len - 1); | |
printf("\n"); | |
} | |
} |
No comments:
Post a Comment