Remove Invalid Parentheses
Intuition
Solution
class Solution:
def __init__(self):
self.string = None
self.min_rem_count = None
self.valid_strings = None
def _reset(self, s):
self.string = s
self.min_rem_count = len(s)
self.valid_strings = set()
def _dfs(self, index, expr, l_count, r_count, rem_count):
# If we meet the end of the string
if index == len(self.string):
if l_count == r_count and rem_count <= self.min_rem_count:
if rem_count < self.min_rem_count:
self.min_rem_count = rem_count
self.valid_strings = set()
self.valid_strings.add(''.join(expr))
return
# Optimize
if rem_count > self.min_rem_count:
return
elif abs(l_count - r_count) > (len(self.string) - index):
return
# Body of this dfs
c = self.string[index]
if r_count > l_count:
return
if c not in '()':
expr.append(c)
self._dfs(index+1, expr, l_count, r_count, rem_count)
expr.pop()
else:
self._dfs(index+1, expr, l_count, r_count, rem_count+1)
if c == '(':
expr.append(c)
self._dfs(index+1, expr, l_count+1, r_count, rem_count)
expr.pop()
elif c == ')':
expr.append(c)
self._dfs(index+1, expr, l_count, r_count+1, rem_count)
expr.pop()
def removeInvalidParentheses(self, s: str) -> List[str]:
self._reset(s)
self._dfs(0, [], 0, 0, 0)
return list(self.valid_strings)
def main():
testcases = [
"(()",
"(a)())()",
")("
]
for case in testcases:
print(case, Solution().removeInvalidParentheses(case))
if __name__ == '__main__':
main()