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

Revision en11, by SPyofgame, 2021-02-04 10:02:38

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 it satisfy one of below

  • $$$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.

The question is that: 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$$$
  • 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))$$$
  • Notice that when $$$S_l$$$ match $$$S_r$$$, $$$F(l, r) = min(F(l + 1, r - 1), 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)$$$


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

Base cases:

  • If $$$l > r$$$ then the string is empty, hence $$$F(l, r) = 0$$$
  • If $$$l = r$$$ then we should add one charactor to match $$$S_l$$$ to make this substring good, hence $$$F(l, r) = 1$$$

Branch and bound cases:

  • If $$$S_l$$$ is close barrack, then add a open barrack before it, hence $$$F(l, r) = F(l + 1, r) + 1$$$
  • If $$$S_r$$$ is open barrack, then add a close barrack after it, hence $$$F(l, r) = F(l, r - 1) + 1$$$
  • If $$$(S_l, S_{l+1})$$$ is good, then just paired it up, hence $$$F(l, r) = F(l + 2, r) + 0$$$
  • If $$$(S_{r-1}, S_r)$$$ is good, then just paired it up, hence $$$F(l, r) = F(l, r - 2) + 0$$$

Main cases:

For each $$$k = l \rightarrow r - 1$$$

  • If $$$S_k$$$ match $$$S_r$$$, minimize $$$F(l, r)$$$ with $$$F(l, k - 1) + 0 + F(k + 1, r - 1)$$$
  • Else add a open charactor at k to match $$$S_r$$$, minimize $$$F(l, r)$$$ with $$$F(l, k) + 1 + F(k + 1, r - 1)$$$
Recursive 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)$$$ or $$$O(1)$$$ for transistion
  • Hence the upper bound complexity is $$$O(n^3)$$$
  • Hence the lower bound complexity is $$$O(n^2)$$$


My question

  • If the string $$$S$$$ is only consist of '(' and ')' then there is a Linear ($$$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)