class Solution(object):
def checkValidString(self, s):
"""
:type s: str
:rtype: bool
"""
cnt = 0
for s1 in s:
if s1=='(' or s1=='*':
cnt += 1
if s1==')':
cnt -= 1
if cnt<0:
return False
if cnt==0:
return True
cnt = 0
for s1 in s[::-1]:
if s1==')' or s1=='*':
cnt += 1
if s1=='(':
cnt -= 1
if cnt<0:
return False
return True
1 因为*可以当做（，也可以当做），那我们就分两种情况判断，先把*当做（判断，然后再判断*为）的情况
2 同时使用一个计数的变量，遇到（ 就加，遇到 ）就减
3 第一种情况：当cnt为负的时候就返回False
4 第二种情况：首先需要将string reverse一下，这样才是pair的概念，遇到一个），cnt加1，遇到（，就减1，代表消除一对
5 如果两种情况都满足要求的话，就返回True
6 第一种情况下，当最终cnt为0时，我们可以直接返回True。当cnt为正数的时候，我们不能返回False，因为有可能多余的（是*变来的，*可以表示为空
7 第二种情况下，如果最终cnt为0，返回True，如果cnt为正，说明有多余），这又分成两种情况，一种是*变成）导致多余的，另一种是）多余。在第一种情况的时候，如果是左括号多了，会在这种情况下检测出来，如果没有检测出来，说明就是星号变成的左括号。这些星号在第二种情况下又变成了右括号
8 在做反向遍历的时候，cnt要重新置0
