删除无效的括号

https://www.lintcode.com/problem/780/solution/17902?utm_source=sc-libao-ql

miao述

删除最小数目的无效括号，使得输入字符串有效，返回所有可能的结果。

输入字符串可能包含除括号( 和 )之外的字符。

样例

样例 1:

输入:"()())()"输出:["(())()","()()()"]

样例 2:

输入:"(a)())()"输出: ["(a)()()", "(a())()"]

样例 3:

输入:")(" 输出: [""]

分析：

dfs or bfs。

dfs：得到应该移除的左右括号数字。然后dfs试探每个字符是否可以移除。

状态转移有2个变量：去掉某个字符后剩下的str和遍历的起始点start。这里start在循环时保持不变，因为它本是前面函数的start+1位置，这样保证了递归函数从新str的start位置继续遍历下去。

注意去重： if i != start and s[i] == s[i-1] 保证了无重复。

from typing import List

class Solution:
    """
    @param s: The input string
    @return: Return all possible results
    """
    def remove_invalid_parentheses(self, s: str) -> List[str]:
        res = []
        
        def helper(s, start, l_remove, r_remove):
            if l_remove == 0 and r_remove==0:
                if is_valid(s):
                    res.append(s)
            #     return 
            # if l_remove + r_remove > len(s): #剩下的s太短，不够移除
            #     return

            for i in range(start, len(s)): #试探每个字符是否可以移除
                if i != start and s[i] == s[i-1]: #重复的字符移第一个就行,这里是去重，结果就无需set
                    continue
                c = s[i]
                if c == '(' and l_remove > 0:
                    helper(s[:i]+s[i+1:], i, l_remove - 1, r_remove)
                if c == ')' and r_remove > 0:
                    helper(s[:i]+s[i+1:], i, l_remove, r_remove - 1)
     
        def is_valid(string):
            l, r = count_left_right_remove(string)
            return l == 0 and r == 0

        def count_left_right_remove(s):
            l_remove, r_remove = 0, 0
            for char in s:
                if char == '(':
                    l_remove += 1
                elif char == ')':
                    if l_remove > 0:
                        l_remove -= 1
                    else:
                        r_remove += 1
            return l_remove, r_remove

        l_remove, r_remove = count_left_right_remove(s)
        helper(s, 0, l_remove, r_remove)
        
        return res

bfs