## 题目描述：

LeetCode 678. Valid Parenthesis String

Given a string containing only three types of characters: '(', ')' and '*', write a function to check whether this string is valid. We define the validity of a string by these rules:

1. Any left parenthesis `'('` must have a corresponding right parenthesis `')'`.
2. Any right parenthesis `')'` must have a corresponding left parenthesis `'('`.
3. Left parenthesis `'('` must go before the corresponding right parenthesis `')'`.
4. `'*'` could be treated as a single right parenthesis `')'` or a single left parenthesis `'('` or an empty string.
5. An empty string is also valid.

Example 1:

```Input: "()"
Output: True
```

Example 2:

```Input: "(*)"
Output: True
```

Example 3:

```Input: "(*))"
Output: True
```

Note:

1. The string size will be in the range [1, 100].

## 解题思路：

```遍历s中的字符c，利用集合vset记录所有当前左括号-右括号的差值

若c == '('，将vset替换为其所有元素+1

若c == ')'，将vset替换为其所有不小于1的元素 - 1

若c == '*’，将vset中的所有元素+1，-1后，保留非负元素

## Python代码：

``````class Solution(object):
def checkValidString(self, s):
"""
:type s: str
:rtype: bool
"""
vset = set([0])
for c in s:
nset = set()
if c == '*':
for v in vset:
if v >= 1: nset.add(v - 1)
elif c == '(':
for v in vset:
elif c == ')':
for v in vset:
if v >= 1: nset.add(v - 1)
vset = nset
return 0 in vset
``````

Pingbacks已关闭。