valid_parentheses_string
1from functools import cache 2 3 4# @leet start 5class Solution: 6 def checkValidString(self, s: str) -> bool: 7 """ 8 This question asks if a parentheses string that contains either 9 '(', ')' or '*' is valid, where '*' can be an empty string or either open 10 or closed paren. 11 12 You can do this either with DP in $O(n^2)$ time and $O(n^2)$ space 13 or you can do it greedily in $O(n)$ time and $O(1)$ space. 14 15 The greedy approach looks like this, where you iterate forwards and 16 backwards through the string, and increment the open paren count when 17 you encounter a '(' or a '*' and increment the close paren count when 18 you encounter a ')' or a '*', otherwise decrement both. 19 20 If through the loop either open or close count are < 0, we return False. 21 """ 22 open_count = 0 23 close_count = 0 24 n = len(s) - 1 25 26 for i in range(len(s)): 27 if s[i] == "(" or s[i] == "*": 28 open_count += 1 29 else: 30 open_count -= 1 31 32 if s[n - i] == ")" or s[n - i] == "*": 33 close_count += 1 34 else: 35 close_count -= 1 36 37 if open_count < 0 or close_count < 0: 38 return False 39 return True 40 41 def dp(self, s: str) -> bool: 42 """ 43 To do this in the DP fashion, we can note that '(' should increase 44 our paren count by 1, ')' should decrease it by 1, and '*' can either 45 increase (if acts as '('), decrease (as ')') or do nothing (as '') to the count. 46 47 '*' can act as all outcomes, so when we encounter that, we have to DFS 48 through all possible outcomes. 49 50 We can then dfs through in each case, making sure our paren_count never 51 drops below 0 and return the result. 52 """ 53 54 @cache 55 def dfs(s, paren_count): 56 if paren_count < 0: 57 return False 58 if not s: 59 return paren_count == 0 60 if s[0] == "(": 61 return dfs(s[1:], paren_count + 1) 62 if s[0] == ")": 63 return dfs(s[1:], paren_count - 1) 64 return ( 65 dfs(s[1:], paren_count + 1) 66 or dfs(s[1:], paren_count - 1) 67 or dfs(s[1:], paren_count) 68 ) 69 70 return dfs(s, 0) 71 72 73# @leet end 74 75 76def test(): 77 assert 2 + 2 == 4
class
Solution:
6class Solution: 7 def checkValidString(self, s: str) -> bool: 8 """ 9 This question asks if a parentheses string that contains either 10 '(', ')' or '*' is valid, where '*' can be an empty string or either open 11 or closed paren. 12 13 You can do this either with DP in $O(n^2)$ time and $O(n^2)$ space 14 or you can do it greedily in $O(n)$ time and $O(1)$ space. 15 16 The greedy approach looks like this, where you iterate forwards and 17 backwards through the string, and increment the open paren count when 18 you encounter a '(' or a '*' and increment the close paren count when 19 you encounter a ')' or a '*', otherwise decrement both. 20 21 If through the loop either open or close count are < 0, we return False. 22 """ 23 open_count = 0 24 close_count = 0 25 n = len(s) - 1 26 27 for i in range(len(s)): 28 if s[i] == "(" or s[i] == "*": 29 open_count += 1 30 else: 31 open_count -= 1 32 33 if s[n - i] == ")" or s[n - i] == "*": 34 close_count += 1 35 else: 36 close_count -= 1 37 38 if open_count < 0 or close_count < 0: 39 return False 40 return True 41 42 def dp(self, s: str) -> bool: 43 """ 44 To do this in the DP fashion, we can note that '(' should increase 45 our paren count by 1, ')' should decrease it by 1, and '*' can either 46 increase (if acts as '('), decrease (as ')') or do nothing (as '') to the count. 47 48 '*' can act as all outcomes, so when we encounter that, we have to DFS 49 through all possible outcomes. 50 51 We can then dfs through in each case, making sure our paren_count never 52 drops below 0 and return the result. 53 """ 54 55 @cache 56 def dfs(s, paren_count): 57 if paren_count < 0: 58 return False 59 if not s: 60 return paren_count == 0 61 if s[0] == "(": 62 return dfs(s[1:], paren_count + 1) 63 if s[0] == ")": 64 return dfs(s[1:], paren_count - 1) 65 return ( 66 dfs(s[1:], paren_count + 1) 67 or dfs(s[1:], paren_count - 1) 68 or dfs(s[1:], paren_count) 69 ) 70 71 return dfs(s, 0)
def
checkValidString(self, s: str) -> bool:
7 def checkValidString(self, s: str) -> bool: 8 """ 9 This question asks if a parentheses string that contains either 10 '(', ')' or '*' is valid, where '*' can be an empty string or either open 11 or closed paren. 12 13 You can do this either with DP in $O(n^2)$ time and $O(n^2)$ space 14 or you can do it greedily in $O(n)$ time and $O(1)$ space. 15 16 The greedy approach looks like this, where you iterate forwards and 17 backwards through the string, and increment the open paren count when 18 you encounter a '(' or a '*' and increment the close paren count when 19 you encounter a ')' or a '*', otherwise decrement both. 20 21 If through the loop either open or close count are < 0, we return False. 22 """ 23 open_count = 0 24 close_count = 0 25 n = len(s) - 1 26 27 for i in range(len(s)): 28 if s[i] == "(" or s[i] == "*": 29 open_count += 1 30 else: 31 open_count -= 1 32 33 if s[n - i] == ")" or s[n - i] == "*": 34 close_count += 1 35 else: 36 close_count -= 1 37 38 if open_count < 0 or close_count < 0: 39 return False 40 return True
This question asks if a parentheses string that contains either '(', ')' or '' is valid, where '' can be an empty string or either open or closed paren.
You can do this either with DP in $O(n^2)$ time and $O(n^2)$ space or you can do it greedily in $O(n)$ time and $O(1)$ space.
The greedy approach looks like this, where you iterate forwards and backwards through the string, and increment the open paren count when you encounter a '(' or a '' and increment the close paren count when you encounter a ')' or a '', otherwise decrement both.
If through the loop either open or close count are < 0, we return False.
def
dp(self, s: str) -> bool:
42 def dp(self, s: str) -> bool: 43 """ 44 To do this in the DP fashion, we can note that '(' should increase 45 our paren count by 1, ')' should decrease it by 1, and '*' can either 46 increase (if acts as '('), decrease (as ')') or do nothing (as '') to the count. 47 48 '*' can act as all outcomes, so when we encounter that, we have to DFS 49 through all possible outcomes. 50 51 We can then dfs through in each case, making sure our paren_count never 52 drops below 0 and return the result. 53 """ 54 55 @cache 56 def dfs(s, paren_count): 57 if paren_count < 0: 58 return False 59 if not s: 60 return paren_count == 0 61 if s[0] == "(": 62 return dfs(s[1:], paren_count + 1) 63 if s[0] == ")": 64 return dfs(s[1:], paren_count - 1) 65 return ( 66 dfs(s[1:], paren_count + 1) 67 or dfs(s[1:], paren_count - 1) 68 or dfs(s[1:], paren_count) 69 ) 70 71 return dfs(s, 0)
To do this in the DP fashion, we can note that '(' should increase our paren count by 1, ')' should decrease it by 1, and '*' can either increase (if acts as '('), decrease (as ')') or do nothing (as '') to the count.
'*' can act as all outcomes, so when we encounter that, we have to DFS through all possible outcomes.
We can then dfs through in each case, making sure our paren_count never drops below 0 and return the result.
def
test():