leetcode/python/0678-valid-parenthesis-string.py at main · ColstonBod-oy/leetcode · GitHub

Name: leetcode/python/0678-valid-parenthesis-string.py at main · ColstonBod-oy/leetcode · GitHub
Rating: 4.8 (4571 reviews)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# Dynamic Programming: O(n^2)
classSolution:
defcheckValidString(self, s: str) ->bool:
dp= {(len(s), 0): True} # key=(i, leftCount) -> isValid

defdfs(i, left):
ifi==len(s) orleft<0:
returnleft==0
if (i, left) indp:
returndp[(i, left)]

ifs[i] =="(":
dp[(i, left)] =dfs(i+1, left+1)
elifs[i] ==")":
dp[(i, left)] =dfs(i+1, left-1)
else:
dp[(i, left)] = (
dfs(i+1, left+1) ordfs(i+1, left-1) ordfs(i+1, left)
 )
returndp[(i, left)]

returndfs(0, 0)


# Greedy: O(n)
classSolution:
defcheckValidString(self, s: str) ->bool:
leftMin, leftMax=0, 0

forcins:
ifc=="(":
leftMin, leftMax=leftMin+1, leftMax+1
elifc==")":
leftMin, leftMax=leftMin-1, leftMax-1
else:
leftMin, leftMax=leftMin-1, leftMax+1
ifleftMax<0:
returnFalse
ifleftMin<0: # required because -> s = ( * ) (
leftMin=0
returnleftMin==0