```
class Solution(object):
def checkValidString(self, s):
"""
:type s: str
:rtype: bool
"""
m = len(s)
if m == 0: return True
f = [set() for i in xrange(m + 1)]
f[0].add(0)
for i in xrange(1, m + 1):
for v in f[i-1]:
if s[i-1] == '(':
f[i].add(v + 1)
elif s[i-1] == ')':
if v - 1 >= 0:
f[i].add(v-1)
else:
f[i].add(v + 1)
if v - 1 >= 0:
f[i].add(v - 1)
f[i].add(v)
return 0 in f[m]
```