301. Delete invalid brackets

301. Remove invalid brackets

Original title link ：https://leetcode.cn/problems/remove-invalid-parentheses/

Here's a string of parentheses and letters s , Remove the minimum number of invalid parentheses , Make the input string valid .

Returns all possible results . You can press In any order return .

Example 1：

Input ：s = “()())()”
Output ：[“(())()”,“()()()”]
Example 2：

Input ：s = “(a)())()”
Output ：[“(a())()”,“(a)()()”]
Example 3：

Input ：s = “)(”
Output ：[“”]

Tips ：

1 <= s.length <= 25
s It consists of lowercase English letters and parentheses ‘(’ and ‘)’ form
s At most 20 A bracket

Their thinking ：

First count the number of redundant left and right parentheses , Then recursively delete the extra parentheses , Remaining reservations .

Code implementation ：

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        #  Statistics s The superfluous ( That is, the left and right do not match ) Number of left and right parentheses 
        l = r = 0
        for c in s:
            if c == '(':
                l += 1
            elif c == ')':
                if l:
                    l -= 1
                else:
                    r += 1

        ans = []

        @lru_cache(None)
        def dfs(idx, cur_left, cur_right, del_left, del_right, path):
            #  Recursive function dfs:  from idx Position start , Delete redundant left 、 Close the parenthesis or keep the current character 
            # cur_left,cur_right Respectively, count the current number of left and right parentheses 
            # del_left,del_right It is to count the number of left and right parentheses deleted at present 
            
            #  If the traversed position and s Equal length , That is, there are no redundant left and right parentheses 
            if idx == len(s):
                if not del_left and not del_right:
                    ans.append(path)
                return 
            #  If you want the current right bracket to be more than the left bracket to be deleted , Or the number of left and right parentheses to be deleted is less than 0
            if cur_right > cur_left or del_left < 0 or del_right < 0:
                return 
            
            c = s[idx]
            #  First delete the redundant number of left and right parentheses counted by the previous function 
            if c == '(':
                dfs(idx + 1, cur_left, cur_right, del_left - 1, del_right, path)
            elif c == ')':
                dfs(idx + 1, cur_left, cur_right, del_left, del_right - 1, path)

            #  Recurse to the next position 
            dfs(idx + 1, cur_left + int(c == '('), cur_right + int(c == ')'), del_left, del_right, path + c)

        
        dfs(0, 0, 0, l, r, "")

        return ans

reference ：

https://leetcode.cn/problems/remove-invalid-parentheses/solution/python-ji-yi-hua-dfs-by-himymben-5b18/