301 Remove Invalid Parentheses

https://leetcode.com/problems/remove-invalid-parentheses/

solution

# 1. 遍历，记录下需要移除的左括号数量和右括号数量
# 2. DFS/回溯, 每一个新的字符，我们都有两个选择：'留' 或者 '不留'

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        l, r = self.get_lr(s)
        res = []
        start = 0
        self.dfs(s, res, start, l, r)
        return res

    def get_lr(self, s):
        l, r = 0, 0
        for char in s:
            if char == '(':
                l += 1
            elif char == ')':
                if l == 0:
                    r += 1
                else:
                    l -= 1
        return l, r

    def is_valid(self, s):
        stack = []
        for i in range(len(s)):
            if s[i] == '(':
                stack.append(i)
            elif s[i] == ')':
                if stack:
                    stack.pop()
                else:
                    return False
        return len(stack) == 0

    def dfs(self, s, res, start, l, r):
        if l == 0 and r == 0 and self.is_valid(s):
            res.append(s)

        for i in range(start, len(s)):  # for循环来试图删掉每一个字符, 递归继续往下删除
            if i > start and s[i] == s[i-1]:  # 重复判断, 无论是左括号还是右括号
                continue
            if r > 0 and s[i] == ')':  # 每一个位置，可能是去掉左括号，可能去掉右括号
                self.dfs(s[:i] + s[i + 1:], res, i, l, r - 1)
            elif l > 0 and s[i] == '(':
                self.dfs(s[:i] + s[i + 1:], res, i, l - 1, r)

时间复杂度：O(2^n) 空间复杂度：O(n+|ans|)

from collections import deque

class Solution:
    def removeInvalidParentheses(self, s):
        if not s:
            return ['']
        queue = deque([s])
        result, visited = [], set([s])
        found = False
        while queue:
            cur = queue.popleft()
            if self.is_valid_parentheses(cur):
                found = True
                result.append(cur)
            elif not found:
                for i in range(len(cur)):
                    if cur[i] == '(' or cur[i] == ')':
                        t = cur[:i] + cur[i + 1:]
                        if t not in visited:
                            queue.append(t)
                            visited.add(t)
        return result
        
    def is_valid_parentheses(self, s):
        cnt = 0
        for c in s:
            if c == '(':
                cnt += 1 
            elif c == ')':
                if cnt == 0:
                    return False
                cnt -= 1 
        return cnt == 0

follow op

括号类小结

22 Generate Parentheses