leetcode Remove Invalid Parentheses

leetcode Remove Invalid Parentheses

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Examples:

• "()())()" -> ["()()()", "(())()"]
• "(a)())()" -> ["(a)()()", "(a())()"]
• ")(" -> [""]

题目地址：leetcode Remove Invalid Parentheses

题意：

给定一串括号组成的字符串（可能 有其他字符），要求你在去除最少的括号数情况下，使其合法。输出所有结果

思路：

方法一 BFS:

枚举去除的点，当找到后停止BFS树的扩展（因为要去除最少括号，所以即使有其他的结果，也一定在同一层）

class Solution(object):
    def removeInvalidParentheses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        if not s: return ['']
        q, ans, vis = [s], [], set([s])
        found = False
        while q:
            cur = q.pop(0)
            if self.isValidParentheses(cur):
                found = True
                ans.append(cur)
            elif not found:
                for i in xrange(len(cur)):
                    if cur[i] == '(' or cur[i] == ')':
                        t = cur[:i] + cur[i + 1:]
                        if t not in vis:
                            q.append(t)
                            vis.add(t)
        return ans

    def isValidParentheses(self, s):
        cnt = 0
        for c in s:
            if c == '(':
                cnt += 1
            elif c == ')':
                if cnt == 0: return False
                cnt -= 1
        return cnt == 0

更简洁的写法

class Solution(object):
    def removeInvalidParentheses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        if not s: return ['']
        q = {s}
        while q:
            ans = filter(self.isValidParentheses,q)
            if ans: return ans
            q = {cur[:i] + cur[i + 1:] for cur in q for i in xrange(len(cur))}

    def isValidParentheses(self, s):
        cnt = 0
        for c in s:
            if c == '(':
                cnt += 1
            elif c == ')':
                if cnt == 0: return False
                cnt -= 1
        return cnt == 0

 

方法二： DFS

统计左右括号能删的个数，进行DFS。

class Solution(object):
    def removeInvalidParentheses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        if not s: return ['']
        left_remove = right_remove = 0
        for c in s:
            if c == '(':
                left_remove += 1
            elif c == ')':
                if left_remove:
                    left_remove -= 1
                else:
                    right_remove += 1

        ans = set()
        self.dfs(0, left_remove, right_remove, 0, '', s, ans)
        return list(ans)

    def dfs(self, index, left_remove, right_remove, left_pare, cur, s, ans):
        if left_remove < 0 or right_remove < 0 or left_pare < 0: return
        if index == len(s):
            if left_remove == right_remove == left_pare == 0:
                ans.add(cur)
            return

        if s[index] == '(':
            self.dfs(index + 1, left_remove - 1, right_remove, left_pare, cur, s, ans)
            self.dfs(index + 1, left_remove, right_remove, left_pare + 1, cur + s[index], s, ans)
        elif s[index] == ')':
            self.dfs(index + 1, left_remove, right_remove - 1, left_pare, cur, s, ans)
            self.dfs(index + 1, left_remove, right_remove, left_pare - 1, cur + s[index], s, ans)
        else:
            self.dfs(index + 1, left_remove, right_remove, left_pare, cur + s[index], s, ans)