2
$\begingroup$

I am currently working on the following problem that involves developing a dynamic programming algorithm for finding the length of the shortest fully bracketed expression (FBE), $y$ that contains a given string $x = x_1x_2...x_n$. An FBE is defined as a string over the characters (,),[, and ] that is either

  1. the empty string
  2. the string $[T]$ or $(T)$, where $T$ is a fully bracketed expression, or
  3. the string $TU$, where $T$ and $U$ are fully bracketed expressions.

So far I have worked through the potential recursive function $T(i,j)$ which I've defined as the length of the shortest possible FBE that contains $x_i...x_j$ as a subsequence (not necessarily a string). And I know that in the shortest FBE containing $x_i...x_j$ that $x_i$ is either "mathced" to an appropriate character $x_k$ such that $i + 1 \leq k \leq j$, or it isn't. So I think that I need two cases; either the former is true, or the latter is true.

I'm having trouble formalizing this and creating a recursion. I'm not sure how to deal with the addition of characters. Any help would be appreciated! Thanks!

$\endgroup$
1
$\begingroup$

Let $S(i,j)$ be the set of the shortest FBEs containing $x_i\ldots x_j$. We focus on non-trivial cases ($j-i\ge 2$).

If there is an element in $S(i,j)$ with the form $AB$ where neither $A$ nor $B$ is empty, there must exist $i\le k<j$ such that $x_i,\ldots, x_k$ belong to $A$ and $x_{k+1},\ldots,x_j$ belongs to $B$. Easy to see $T(i,j)=\min_k\{T(i,k)+T(k+1,j)\}$.

Otherwise, take an element from $S(i,j)$. Assume WLOG it has the form [$A$]. Note $x_{i+1},\ldots,x_{j-1}$ are contained in $A$, we have $T(i,j)\ge T(i+1,j-1)+2$. Furthermore, if either $x_i\neq$ [ or $x_j\neq$ ] (say $x_i\neq$ [ WLOG), then $A$[] (with the form $AB$) is also an FBE containing $x_i\ldots x_j$, which contradicts to the assumption. Hence $x_i$ and $x_j$ must match.

Combining the two paragraphs above, we have proved

  • if $x_i$ and $x_j$ do not match,

$$T(i,j)= \min_k\{T(i,k)+T(k+1,j)\},$$

  • if $x_i$ and $x_j$ match,

$$T(i,j)\ge \min\left\{\min_k\{T(i,k)+T(k+1,j)\}, T(i+1,j-1)+2\right\}.$$

Note concentrating a shortest FBE containing $x_i\ldots x_k$ and a shortest FBE containing $x_{k+1}\ldots x_j$ constitutes an FBE containing $x_i\ldots x_j$, so $T(i,j)\le \min_k\{T(i,k)+T(k+1,j)\}$. In addition, if $x_i$ and $x_j$ match, say $x_i=$ [ and $x_j=$ ], and let $s$ be a shortest FBE containing $x_{i+1}\ldots x_{j-1}$, then [$s$] is an FBE containing $x_i\ldots x_j$, so $T(i,j)\le T(i+1,j-1)+2$. As a conclusion, if $x_i$ and $x_j$ match,

$$T(i,j)\le \min\left\{\min_k\{T(i,k)+T(k+1,j)\}, T(i+1,j-1)+2\right\}.$$

So the recursion turns out to be

  • if $x_i$ and $x_j$ do not match,

$$T(i,j)= \min_k\{T(i,k)+T(k+1,j)\},$$

  • if $x_i$ and $x_j$ match,

$$T(i,j)= \min\left\{\min_k\{T(i,k)+T(k+1,j)\}, T(i+1,j-1)+2\right\}.$$

$\endgroup$
  • $\begingroup$ Thank you, this is very helpful. Now, to deal with the base cases we must account for $j-i = 1$ and $j=i$. I'm thinking if $j=i$ we return 2, and then do we need to check if $x_i$ and $x_j$ match for the $j-i = 1$ case? $\endgroup$ – User1996424 Mar 8 '18 at 19:54
  • $\begingroup$ @JohnBob76 Sure. For $j-i=1$, $T(i,j)=2$ if and only if $x_i$ and $x_j$ match. The argument in this answer still works for $j-i=1$ case if you treat $T(i+1,j-1)=0$ (length of shortest FBE containing an empty sequence is $0$). $\endgroup$ – xskxzr Mar 9 '18 at 1:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.