[LeetCode]Valid Parenthesis String

这道题主要就是如何handle wild card char，一个思路就是保证所有的左括号和右括号都能够被match。我们有几种做法，我们可以维护两个stack，left和wc，分别对应左括号和wild card char。Stack中存对应的左边，如果：

• 当前char为左括号或者wc，push index进相应的stack
• 如果char为右括号
• 如果left有元素，pop left
• 否则，如果wc有元素，pop wc
• 否则，我们无法match当前右括号，return false
• 当我们扫完string后
• 如果left有元素，我们check wc中的元素是否能match left栈顶元素，能的话就pop两个stack的元素
• 如果不能将left清空，return false
• return true

时间复杂度O(n)，空间复杂度O(n)，代码如下：

如果我们想少用点空间，我们可以从左往右看所有的右括号是不是能被match，再从右往左看所有的左括号能不能被match，时间复杂度O(n)，空间复杂度O(1)，代码如下：

还有一种解法可以达到one pass，时间复杂度O(n)，空间复杂度O(1)的解法。和不带wild card char的parenthesis string类似，我们需要维护当前open left bracket的数量，区别是，没有wild card char，open left bracket的数量就是一个确定的数，但是如果加入wild card char之后我们就应该维护一个区间，因为这个区间是连续的我们只需要存区间的最大最小值即可。我们用lo和hi来表示区间的边界：

• 如果当前char为左括号，lo++， hi++
• 如果当前char为右括号，lo--，hi--
• 如果当前char为wild card char，其既可以作为左括号也可以作为右括号，lo--，hi++
• 如果hi < 0，代表当前右括号我们没有办法match，return false（例如 "(*)))"）
• 如果lo < 0, 我们显然不希望lo变为负数，因为其代表中间的一些wild card char被设置成右括号的情况，显然这些情况是不合理的，我们要强制让lo变为0，也就是让部分wild card char变为empty string。例如"(**)("，当我们扫过"(**"的时候应该为[0, 3]而不是[-1, 3]，因为"())"的情况是不合理的。

代码如下：