301 Remove Invalid Parentheses #66
Comments
|
最原始粗暴的方法，直接所有可能性的去找，会有非常多的冗余。 DFS Base Case 在主方程跑完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 finalBrute Forceclass 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为负数的时候进行剪枝 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
|
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
No description provided.
The text was updated successfully, but these errors were encountered: