This problem can be solved elegantly using dynamic programming.
We maintain two arrays:
- cnt[i][j] --- number of parentheses needed to add within s[i..j] inclusively;
- pos[i][j] --- position to add the parenthesis within s[i..j] inclusively.
Then there are three cases:
- cnt[i][i] = 1;
- If s[i] == s[j], cnt[i][j] = cnt[i + 1][j - 1], pos[i][j] = -1 (no need to add any parenthesis);
- If s[i] != s[j], cnt[i][j] = min_{k = i, i + 1, ..., j}cnt[i][k] + cnt[k + 1][j], pos[i][j] = k (choose the best position to add the parenthesis).
After computing cnt and pos, we will print the resulting parentheses recursively.
My accepted code is as follows. In fact, I spent a lot timg on debugging the Wrong Answer error due to incorrect input/output. You may try this problem at this link.
1 #include <iostream> 2 #include <cstdio> 3 #include <vector> 4 #include <cstring> 5 6 using namespace std; 7 8 #define INT_MAX 0x7fffffff 9 #define vec1d vector<int> 10 #define vec2d vector<vec1d > 11 12 void print(char* s, vec2d& pos, int head, int tail) { 13 if (head > tail) return; 14 if (head == tail) { 15 if (s[head] == '(' || s[head] == ')') 16 printf("()"); 17 else printf("[]"); 18 } 19 else if (pos[head][tail] == -1) { 20 printf("%c", s[head]); 21 print(s, pos, head + 1, tail - 1); 22 printf("%c", s[tail]); 23 } 24 else { 25 print(s, pos, head, pos[head][tail]); 26 print(s, pos, pos[head][tail] + 1, tail); 27 } 28 } 29 30 void solve(char* s, vec2d& cnt, vec2d& pos) { 31 int n = strlen(s); 32 for (int i = 0; i < n; i++) 33 cnt[i][i] = 1; 34 for (int l = 1; l < n; l++) { 35 for (int i = 0; i < n - l; i++) { 36 int j = i + l; 37 cnt[i][j] = INT_MAX; 38 if ((s[i] == '(' && s[j] == ')') || (s[i] == '[' && s[j] == ']')) { 39 cnt[i][j] = cnt[i + 1][j - 1]; 40 pos[i][j] = -1; 41 } 42 for (int k = i; k < j; k++) { 43 if (cnt[i][k] + cnt[k + 1][j] < cnt[i][j]) { 44 cnt[i][j] = cnt[i][k] + cnt[k + 1][j]; 45 pos[i][j] = k; 46 } 47 } 48 } 49 } 50 print(s, pos, 0, n - 1); 51 printf("\n"); 52 } 53 54 int main(void) { 55 char s[110]; 56 while (gets(s)) { 57 int n = strlen(s); 58 vec2d cnt(n, vec1d(n, 0)); 59 vec2d pos(n, vec1d(n)); 60 solve(s, cnt, pos); 61 } 62 return 0; 63 }
