leetcode
leetcode copied to clipboard
Published
20 hours ago •
tech-cow
tech-cow
301 Remove Invalid Parentheses
最原始粗暴的方法，直接所有可能性的去找，会有非常多的冗余。
DFS Base Case
只要index到底了，就走一遍isValid
在主方程跑完DFS以后，对得到的答案进行最少更改的检查
for ele in self.res:
max_len = max(max_len, len(ele))
final = []
for ele in self.res:
if len(ele) == max_len:
final.append(ele)
return final
Brute Force
class Solution():
def removeInvalidParentheses(self, s):
self.res = set()
max_len = 0
self.dfs(0, [], s)
'''
After all backtracking, postprocess to find out
the least modification
'''
for ele in self.res:
max_len = max(max_len, len(ele))
final = []
for ele in self.res:
if len(ele) == max_len:
final.append(ele)
return final
def dfs(self, index, temp, s):
'''
backtracking all possible solution with
no pruning for sake
:param temp: list
'''
if index == len(s):
temp_s = ''.join(temp)
if self.isValid(temp_s):
self.res.add(temp_s)
return
temp.append(s[index])
self.dfs(index + 1, temp, s)
temp.pop()
self.dfs(index + 1, temp, s)
def isValid(self, s):
'''
check if a pair of parenthesis is valid
'''
count = 0
for char in s:
if char == '(':
count += 1
if char == ')':
count -= 1
if count < 0:
return False
return count == 0
优化1.
Brute Force的冗余，通过Pruning去省去一些重复计算。
思考的方式可以从需要最少被更改几次出发
计算出左右括号的个数差，然后用函数 change_needed 表示。 在Backtrack过程中，往temp里面增加元素的时候不需要更改这个函数，因为并没有删除任何函数，而在删减的过程中，减少这个函数。
这种方式可以对change_needed为负数的时候进行剪枝
if change_needed < 0:
return
然后对左右括号和其他字符的区分，也进行了一边的剪枝。
优化代码
class Solution():
def removeInvalidParentheses(self, s):
left = right = change_needed = 0
for char in s:
if char == '(':
left += 1
elif char == ')':
if left > 0:
left -= 1
else:
right += 1
change_needed = left + right
self.res = set()
self.dfs(0, [], s, change_needed)
return self.res
def dfs(self, index, temp, s, change_needed):
if change_needed < 0:
return
if index == len(s):
if change_needed == 0:
temp_s = ''.join(temp)
if self.isValid(temp_s):
self.res.add(temp_s)
return
if s[index] == '(' or s[index] == ')':
temp.append(s[index])
self.dfs(index + 1, temp, s, change_needed)
temp.pop()
self.dfs(index + 1, temp, s, change_needed - 1)
else:
temp.append(s[index])
self.dfs(index + 1, temp, s, change_needed)
temp.pop()
def isValid(self, s):
'''
check if a pair of parenthesis is valid
'''
count = 0
for char in s:
if char == '(':
count += 1
if char == ')':
count -= 1
if count < 0:
return False
return count == 0
优化2:
把Temp的Array 变成了 String，减少了一些代码和速度
class Solution():
def removeInvalidParentheses(self, s):
left = right = change_needed = 0
for char in s:
if char == '(':
left += 1
elif char == ')':
if left > 0:
left -= 1
else:
right += 1
change_needed = left + right
self.res = set()
self.dfs(0, '', s, change_needed)
return self.res
def dfs(self, index, temp, s, change_needed):
if change_needed < 0:
return
if index == len(s):
if change_needed == 0:
if self.isValid(temp):
self.res.add(temp)
return
if s[index] == '(' or s[index] == ')':
self.dfs(index + 1, temp + s[index] , s, change_needed)
self.dfs(index + 1, temp, s, change_needed - 1)
else:
self.dfs(index + 1, temp + s[index] , s, change_needed)
def isValid(self, s):
count = 0
for char in s:
if char == '(':
count += 1
if char == ')':
count -= 1
if count < 0:
return False
return count == 0
class Solution:
def removeInvalidParentheses(self, s: str) -> List[str]:
left = right = 0
for c in s:
if c == "(":
left += 1
elif c == ")":
if left == 0:
right += 1
else:
left -= 1
def dfs(depth, left, right, left_rem, right_rem, cur):
if depth == len(s):
if left == right and left_rem == right_rem == 0:
self.ans.add(cur)
return
else:
if s[depth] == "(":
if left_rem > 0:
dfs(depth + 1, left, right, left_rem - 1, right_rem, cur)
dfs(depth + 1, left + 1, right, left_rem, right_rem, cur + "(")
elif s[depth] == ")":
if right_rem > 0:
dfs(depth + 1, left, right, left_rem, right_rem - 1, cur)
if left > right:
dfs(depth + 1, left, right + 1, left_rem, right_rem, cur + ")")
else:
dfs(depth + 1, left, right, left_rem, right_rem, cur + s[depth])
self.ans = set()
dfs(0, 0, 0, left, right, "")
return list(self.ans)
'''
Start: 6:59
# @ [二刷]
Bug 1: findLeftRightDiff() takes exactly 1 arguement
@ Bug
def findLeftRightDiff(s):
@ Fixed
def findLeftRightDiff(self, s):
Bug 2:
@ Bug
else:
self.dfsHelper(s, res, curLeft, curRight, leftDiff, rightDiff, index + 1, temp)
@ Fixed
else:
self.dfsHelper(s, res, curLeft, curRight, leftDiff, rightDiff, index + 1, temp + s[index])
'''
class Solution(object):
def removeInvalidParentheses(self, s):
if not s: return [""]
res = set()
leftDiff, rightDiff = self.findLeftRightDiff(s)
curLeft, curRight = 0, 0
self.dfsHelper(s, res, curLeft, curRight, leftDiff, rightDiff, 0, "")
return res
def dfsHelper(self, s, res, curLeft, curRight, leftDiff, rightDiff, index, temp):
if index == len(s):
if curLeft == curRight and leftDiff == rightDiff == 0:
res.add(temp)
return
else:
if s[index] == '(':
if leftDiff:
self.dfsHelper(s, res, curLeft, curRight, leftDiff - 1, rightDiff, index + 1, temp)
self.dfsHelper(s, res, curLeft + 1, curRight, leftDiff, rightDiff, index + 1, temp + '(')
elif s[index] == ')':
if rightDiff:
self.dfsHelper(s, res, curLeft, curRight, leftDiff, rightDiff - 1, index + 1, temp)
if curRight < curLeft:
self.dfsHelper(s, res, curLeft, curRight + 1, leftDiff, rightDiff, index + 1, temp + ')')
else:
self.dfsHelper(s, res, curLeft, curRight, leftDiff, rightDiff, index + 1, temp + s[index])
def findLeftRightDiff(self, s):
leftDiff, rightDiff = 0, 0
for ch in s:
if ch == '(':
leftDiff += 1
elif ch == ')':
if leftDiff != 0:
leftDiff -= 1
else:
rightDiff += 1
return leftDiff, rightDiff