0678_valid-parenthesis-string

README

0678_valid-parenthesis-string

涉及括号配对的问题, 一般是用两个stack进行操作:

1. 原输入string是一个stack(stack1), top即end.
2. 建立新的stack2:
   • stack1的top是)时, pop并push进stack2.
   • stack1的top是(时:
     • 若stack2的top是), 两个stack都pop.
     • 若stack2的top是(, stack1pop, 并push进stack2.
     • 若stack2为空, 必无效, 直接返回false
3. stack1为空时, 若stack2操作结束也为空, 则是valid string.

或者是一个计算数值变化趋势的过程, '(' = +1, ')' = -1, 遍历的过程中累加, 需要确保:

• 累计值在计算过程中不为负
• 累计值最后为0

一个比较形象的生产中的例子就是代码的缩进.

但显然*的加入让事情变复杂了.

特殊输入

• ""有效, 直接返回

dp

如果问题能够被归纳推导, 我们可以尝试用dp.

dp[i][j]代表s的一个区间[i, j)是否为true.

则:

• dp[i][i]为空"", 必为true
• dp[i][i+1]只有在*的情况下为true.
• dp[i][j+1]为true:
  • 当s[j]是*, 且dp[i][j]是true
  • 当s[j]可以是), 即不是(
    • 且能找到一个s[k]可以是(, 即不是), i <= k < j, 构成配对
    • 且被s[k]分割的两个部分, dp[i][k]和dp[k+1][j]为true

greedy

参照前面累加变化趋势的过程.

我们在计算过程中遇见*的话, 会有+1, -1, +0三种选择(这也是暴力算法的三种选择).

那么因为这个选择, 累加值会出现一个上限和一个下限, 因为趋势是连续的, 我们能够确定, 只要计算出上下限, 每个累加值必定有一种方案能够实现.

上限会随着(和*的出现而上升, 随着)的出现下降; 下限会随着)和*的出现下降, 随着)的出现上升.

但是计算过程中:

• 低于0的方案要被舍弃, 这些方案意味着前面有许多个)没有被配对, 不论在后面添加什么符号都无法弥补.
  • 所以下限>= 0
• 上限需要一直维持>= 0, 若出现小于0的情况, 意味着即使尽可能的配对, 仍有)没被配对

计算结束后若是下限仍b包含0的情况, 则这个string可以有效.