Parentheses
check if valid, 須考慮 ')' 在開頭的情況, 遞歸時也要考慮 ’(‘ 個數大於 ’)' 個數
20. Valid Parentheses
def isValid(self, s: str) -> bool:
dic = {')':'(', ']':'[', '}':'{'}
stack = []
for c in s:
if c in dic:
left = '#' if not stack else stack.pop()
if left != dic[c]:
return False
else:
stack.append(c)
return not stack678. Valid Parenthesis String
Given a string containing only three types of characters: '(', ')' and '*', write a function to check whether this string is valid. We define the validity of a string by these rules:
Any left parenthesis
'('must have a corresponding right parenthesis')'.Any right parenthesis
')'must have a corresponding left parenthesis'('.Left parenthesis
'('must go before the corresponding right parenthesis')'.'*'could be treated as a single right parenthesis')'or a single left parenthesis'('or an empty string.An empty string is also valid
"""
Count the lower bound and higher bound of left bracket
If higher bound < 0, means it can't be valid in current position and afterward
Check if lower bound == 0 when return
"""
def checkValidString(self, s: str) -> bool:
lo, hi = 0, 0
for c in s:
lo += 1 if c == '(' else -1
hi += 1 if c in '(*' else -1
if hi < 0: return False
if lo < 0: lo = 0
return lo == 022. Generate Parentheses
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
n = 3
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
] def generateParenthesis(self, n: int) -> List[str]:
ans = []
def backtracking(s, left, right):
if len(s) == 2*n:
ans.append(s)
return
if left < n:
backtracking(s+'(', left+1, right)
if right < left:
backtracking(s+')', left, right+1)
backtracking('', 0, 0)
return ans 32. Longest Valid Parentheses
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
dp
State: dp[i], s[:i+1]的LVP
Tran: only consider s[i] == ')', dp[i] = dp[i-2] + 2 if s[i-1] == '(' dp[i] = dp[i-dp[i-1]-1] + 2 if s[i-1] = ')' + dp[i-dp[i-1]-2] if i-dp[i-1]-2 >= 0
def longestValidParentheses(self, s: str) -> int:
dp = [0] * len(s)
ans = 0
for i in range(1, len(s)):
if s[i] == ')':
if s[i-1] == '(':
dp[i] = 2 + (dp[i-2] if i-2 >= 0 else 0)
elif i-dp[i-1]-1 >= 0 and s[i-dp[i-1]-1] == '(':
dp[i] = 2 + dp[i-1]
if i-dp[i-1]-2 >= 0:
dp[i] += dp[i-dp[i-1]-2]
ans = max(ans, dp[i])
return ansList double end traverse
There are only three cases for a string:
'(' are more than ')'
'(' are less than ')'
'(' and ')' are the same
Now, when you scan from left to right, you can only find the correct maxLength for cases 2 and 3, because if it is case 1, where '(' are more than ')' (e.g., "((()"), then left is always greater than right and maxLength does not have the chance to be updated.
def longestValidParentheses(self, s: str) -> int:
left, right = 0, 0 ans = 0
for c in s:
if c == '(': left+=1
else: right+=1
if left == right:
ans = max(ans, right*2)
elif right > left:
left, right = 0, 0
left, right = 0, 0
for c in s[::-1]:
if c == '(': left+=1
else: right+=1
if left == right:
ans = max(ans, right*2)
elif left > right:
left, right = 0, 0
return ans1190. Reverse Substrings Between Each Pair of Parentheses
You are given a string s that consists of lower case English letters and brackets. Reverse the strings in each pair of matching parentheses, starting from the innermost one.
Input: s = "(abcd)"
Output: "dcba"Time: O(n^2), Space: O(n)
def reverseParentheses(self, s: str) -> str:
line = ''
stack = []
for c in s:
if c == '(':
stack.append(line)
line = ''
elif c == ')':
pre = stack.pop()
pre += line[::-1]
line = pre
else:
line += c
return lineTime: O(n) for 2 passes, see Lee's explanation
921. Minimum Add to Make Parentheses Valid
Given a string S of '(' and ')' parentheses, we add the minimum number of parentheses ( '(' or ')', and in any positions ) so that the resulting parentheses string is valid.
def minAddToMakeValid(self, S: str) -> int:
balance = 0
count = 0
for c in S:
balance += 1 if c == '(' else -1
# right bracket is greater, must add a left bracket
if balance == -1:
count += 1
balance = 0
# rest of left brackets
return count + balance1249. Minimum Remove to Make Valid Parentheses
Your task is to remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parentheses string is valid and return any valid string.
Formally, a parentheses string is valid if and only if:
It is the empty string, contains only lowercase characters, or
It can be written as
AB(Aconcatenated withB), whereAandBare valid strings, orIt can be written as
(A), whereAis a valid string.
"""
record the index should be removed and rebuild the string
"""
def minRemoveToMakeValid(self, s: str) -> str:
stack = [] # record left parentheses to remove
remove = set() # record right parenthesese to remove
for i, c in enumerate(s):
if c not in '()': continue
if c == '(':
stack.append(i)
# "))((" 的情況
elif c == ')' and not stack:
remove.add(i)
else:
stack.pop()
remove = remove.union(set(stack))
build = ''
for i in range(len(s)):
if i not in remove:
build += s[i]
return build301. Remove Invalid Parentheses
example
Input: "()())()"
Output: ["()()()", "(())()"]先計算 需要remove 多少 '(' and ')'
Backtracking, 適當剪支, 符合條件加入答案(利用set, 因為可能重複)
def removeInvalidParentheses(self, s: str) -> List[str]:
# count invalid '(' and ')'
left, right = 0, 0
for c in s:
if c == '(':
left += 1
elif c == ')':
if left == 0:
right += 1
else:
left -= 1
self.ans = set()
self.dfs(s, 0, 0, 0, left, right, '')
return list(self.ans)
def dfs(self, s, idx, l, r, left_rem, right_rem, exp):
if idx == len(s):
if left_rem == right_rem == 0:
self.ans.add(exp)
return
c = s[idx]
# ignore c either keep c 分開討論
if c == '(':
self.dfs(s, idx+1, l+1, r, left_rem, right_rem, exp+c)
if left_rem > 0:
self.dfs(s, idx+1, l, r, left_rem-1, right_rem, exp)
elif c == ')':
# prune, 只有 r < l 才進行 recursion
if l > r:
self.dfs(s, idx+1, l, r+1, left_rem, right_rem, exp+c)
if right_rem > 0:
self.dfs(s, idx+1, l, r, left_rem, right_rem-1, exp)
# c is letter
else:
self.dfs(s, idx+1, l, r, left_rem, right_rem, exp+c)Last updated
Was this helpful?