For this problem, we update all status space with each chars in string s. Each status is the count of unpaired '(', at each update we only keep 0 and positive counts and remove replicated count with set() data structure. We return true only if we have at least one 0 count in the final status space.

For example, "((**)":

initial: current_step = ([0])

"(": current_step = ([1])

"((": current_step = ([2])

"((*": current_step = ([1, 2, 3])

"((**": current_step = ([0, 1, 2, 3, 4])

"((**)": current_step = ([0, 1, 2, 3])

Time and space complexity analysis:

The worst case is a string contains 100 "*"(since we only scale the status space when we meet "*"), you may find that we only keep non-negative unique status(remove all replicates), the minimum count is 0 and maximum count is 100. So the space complexity is O(n)

Since we search all status space for each chars in string s, time complexity is O(n^2)

```
class Solution(object):
def checkValidString(self, s):
"""
:type s: str
:rtype: bool
"""
if not s:
return True
current_step, next_step = set([0]), set()
for ch in s:
while current_step:
num = current_step.pop()
if ch == '(':
next_step.add(num + 1)
elif ch == ')':
if num - 1 >= 0:
next_step.add(num - 1)
else:
next_step.add(num)
next_step.add(num + 1)
if num - 1 >= 0:
next_step.add(num - 1)
current_step, next_step = next_step, current_step
if current_step and 0 in current_step:
return True
return False
```