题目地址：https://leetcode.com/problems/valid-parenthesis-string/description/
题目描述：
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、 Anyleftparenthesis'('musthaveacorrespondingrightparenthesis')'.；
2、 Anyrightparenthesis')'musthaveacorrespondingleftparenthesis'('.；
3、 Leftparenthesis'('mustgobeforethecorrespondingrightparenthesis')'.；
4、 '*'couldbetreatedasasinglerightparenthesis')'orasingleleftparenthesis'('oranemptystring.；
5、 Anemptystringisalsovalid.；
Example 1:
Input: "()"
Output: True
Example 2:
Input: "(*)"
Output: True
Example 3:
Input: "(*))"
Output: True
Note:
1、 Thestringsizewillbeintherange[1,100].；
题目大意
判断一个括号表达是是否合法，其中包含了*号，*可以表示(,)或者空字符。
解题方法
看到括号表达式第一感觉肯定是栈了。但是由于*的存在，导致这么做并不合理。
又是我绞尽脑汁也做不出来的题，果然还是书影博客open in new window浅显易懂啊！真大神，我跟着学习了不少。
这个思路是这样的：用一个set集合来记录这个表达式中左括号能比右括号多的个数。注意，是能够。因此，如果遇到左括号，集合里面的每个元素应该+1；遇到右括号，如果集合里边的>0的元素可以-1；如果遇到*，应该+1，-1或者不运算。看最后这个集合能否包含0，即左括号的个数等于右括号的个数。
那这个算法怎么判断的")("呢？巧妙的地方就在于，只有set里面大于0的元素才去-1；因此刚开始set只有0元素，所以)不算数。所以这个方法真的很巧妙。
class Solution(object):
def checkValidString(self, s):
"""
:type s: str
:rtype: bool
"""
old_set = set([0])
for c in s:
new_set = set()
if c == '(':
for t in old_set:
new_set.add(t + 1)
elif c == ')':
for t in old_set:
if t > 0:
new_set.add(t - 1)
elif c == '*':
for t in old_set:
new_set.add(t + 1)
new_set.add(t)
if t > 0:
new_set.add(t - 1)
old_set = new_set
return 0 in old_set
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发