rohangulati92's blog

By rohangulati92, 12 years ago, In English

Can anybody provide me a hint for this problem. I am not able to get what the dp states should be.

Thanks in advance.

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
12 years ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

DP states?! This problem is solved using a very stupid greedy algo.

Oh, I understand it's a bit more difficult.

Seems that in order to make some bracket sequence regular, you have 4 different choices:

  1. If the first and the last brackets of the sequence are of the same type and match each other (I mean: the first is opening and the last is closing), you can just throw them away and make the remaining subsequence regular.
  2. If the first bracket is opening, you can append a closing bracket to the end, throw both away and go to the remainder.
  3. If the last bracket is closing, the case will be symmetrical to case 2.
  4. You can split the sequence into two non-zero sized parts and make both regular.

These ideas give an O(N^3) DP solution.

»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks