Minimum number of charactor need to add to make a valid barrack string

Revision en7, by SPyofgame, 2021-02-04 07:18:50

Target: Optimize $$$dp[l][r] = min(dp[l][k] + dp[k + 1][r])$$$ into $$$O(n^2\ polylog)$$$ or lower

My detailed question is below



The statement

A pair of charactor $$$(L, R)$$$ is called good or matched to each other if

  • $$$L =$$$ '(' and $$$R =$$$ ')'
  • $$$L =$$$ '[' and $$$R =$$$ ']'
  • $$$L =$$$ '{' and $$$R =$$$ '}'

Notice that if $$$(L, R)$$$ is good then $$$(R, L)$$$ is not good

String can have many variation of categories, one of that is good string. Let a string $$$S$$$ of size $$$N$$$ is called good if

  • $$$S$$$ is empty (its length $$$N = 0$$$)
  • $$$S = S_1 + S_2 + \dots + S_n$$$. Where $$$S_i$$$ is a good string and + symbol mean that string concaternation
  • $$$S = L + S_x + R$$$ where $$$S_x$$$ is a good string and $$$(L, R)$$$ is a good pair of charactor

Given a string $$$S$$$ of size $$$N$$$. We can add some charactor '(', ')', '[', ']', '{', '}' into anywhere in string $$$S$$$ but you cant replace or remove them. What is the minimum number of charactor need to add into string to make it good ?



The dynamic programming solution $$$O(n^3)$$$

Lets $$$F(l, r)$$$ is the answer for substring $$$S[l..r]$$$.

  • If $$$l > r$$$ then the string is empty, hence the answer is $$$F(l, r) = 0$$$
  • If $$$l = r$$$ then we should add one charactor to match $$$S_l$$$ to make this substring good, hence the answer is $$$F(l, r) = 1$$$
  • If $$$S_l$$$ match $$$S_r$$$, the outside is already make a pair, so $$$F(l, r) = F(l + 1, r - 1) + 0$$$
  • Else we can split into 2 other substring $$$S[l..r] = S[l..k] + S[k+1..r]$$$, for each $$$k$$$ we have $$$F(l, r) = F(l, k) + F(k+1, r)$$$ hence $$$F(l, r) = min(F(l, k) + F(k+1, r))$$$
Recursive Code
Iterative Code
Full Code

Complexity:

  • $$$F(l, r)$$$ have $$$O(n^2)$$$ states
  • In each substring $$$S[l..r]$$$, we maybe to have a for-loop $$$O(n)$$$
  • Hence the upper bound of the complexity is $$$O(n^3)$$$


My question

  • If the string $$$S$$$ is consist of '(' and ')' then there is a $$$O(n)$$$ solution
The solution
  • Can my algorithm ($$$dp[l][r] = min(dp[l][k] + dp[k + 1][r])$$$) improved into $$$O(n^2\ polylog)$$$ or lower in somehow ?

  • Failed to use Knuth algorithm $$$(dp[l][r] = min(dp[l][k] + dp[k][r] + cost[l][r])$$$ since fully-motone condition is not satisfied

Tags string, parentheses, dp, #3d-dp

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en14 English SPyofgame 2021-02-05 13:56:41 7556
en13 English SPyofgame 2021-02-04 10:55:27 273
en12 English SPyofgame 2021-02-04 10:53:42 256
en11 English SPyofgame 2021-02-04 10:02:38 5508
en10 English SPyofgame 2021-02-04 09:43:38 97
en9 English SPyofgame 2021-02-04 08:02:15 303
en8 English SPyofgame 2021-02-04 07:39:33 58
en7 English SPyofgame 2021-02-04 07:18:50 2
en6 English SPyofgame 2021-02-04 07:18:24 183
en5 English SPyofgame 2021-02-04 07:13:19 192
en4 English SPyofgame 2021-02-04 06:10:26 1008
en3 English SPyofgame 2021-02-04 05:56:52 3217
en2 English SPyofgame 2021-02-04 05:10:01 76
en1 English SPyofgame 2021-02-04 05:08:52 3831 Initial revision (published)