Python DFS Solution


  • 4

    The basic idea is recursive DFS with pruning function.

    Generate new strings by removing parenthesis, and calculate the total number of mismatched parentheses inside the string by function calc(s).

    If the mismatched parentheses increased, then discard the string.

    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])    
            return dfs(s)
    

    ref: http://bookshadow.com/weblog/2015/11/05/leetcode-remove-invalid-parentheses/


Log in to reply
 

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