Description
https://leetcode.com/problems/remove-invalid-parentheses/
Given a string s that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid.
Return all the possible results. You may return the answer in any order.
Example 1:
Input: s = "()())()" Output: ["(())()","()()()"]
Example 2:
Input: s = "(a)())()" Output: ["(a())()","(a)()()"]
Example 3:
Input: s = ")("
Output: [""]
Constraints:
1 <= s.length <= 25sconsists of lowercase English letters and parentheses'('and')'.- There will be at most
20parentheses ins.
Explanation
Use depth-first search to find valid strings.
Python Solution
class Solution:
def removeInvalidParentheses(self, s: str) -> List[str]:
results = []
left, right = self.left_right_count(s)
self.dfs_helper(s, left, right, 0, results)
return results
def left_right_count(self, s):
left = 0
right = 0
for c in s:
if c == '(':
left += 1
elif c == ')':
if left > 0:
left -= 1
else:
right += 1
return left, right
def is_valid(self, s):
left, right = self.left_right_count(s)
return left == 0 and right == 0
def dfs_helper(self, s, left, right, start, results):
if left == 0 and right == 0:
if self.is_valid(s):
results.append(s)
return
for i in range(start, len(s)):
if i > start and s[i] == s[i - 1]:
continue
if s[i] == '(':
self.dfs_helper(s[:i] + s[i + 1:], left - 1, right, i, results)
elif s[i] == ')':
self.dfs_helper(s[:i] + s[i + 1:], left, right - 1, i, results)
- Time Complexity: O(N).
- Space Complexity: O(N).