REMOVE INVALID PARENTHESES


  • 0
    Z
    class Solution(object):
        def removeInvalidParentheses(self, s):
            """
            :type s: str
            :rtype: List[str]
            """
            def dfs(s):
                mi = calc(s)
                if mi == 0:
                    return [s]
                ans = []
                for x in range(len(s)):
                    if s[x] in ('(', ')'):
                        ns = s[:x] + s[x+1:]
                        if ns not in visited and calc(ns) < mi:
                            visited.add(ns)
                            ans.extend(dfs(ns))
                return ans    
            def calc(s):
                a = b = 0
                for c in s:
                    a += {'(' : 1, ')' : -1}.get(c, 0)
                    b += a < 0
                    a = max(a, 0)
                return a + b
    
            visited = set([s])    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.