0301._Remove_Invalid_Parentheses.md

301. Remove Invalid Parentheses

难度: Hard

刷题内容

原题连接

• https://leetcode.com/problems/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 ).

Example 1:

Input: "()())()"
Output: ["()()()", "(())()"]
Example 2:

Input: "(a)())()"
Output: ["(a)()()", "(a())()"]
Example 3:

Input: ")("
Output: [""]

解题方案

思路 1 - 时间复杂度: O(2^N)- 空间复杂度: O(N)******

直接抄的stefan

self-explanatory

beats 43.00%

class Solution:
    def removeInvalidParentheses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        def isValid(s):
            cnt = 0
            for c in s:
                if c == '(':
                    cnt += 1
                elif c == ')':
                    cnt -= 1
                    if cnt < 0:
                        return False
            return cnt == 0
        
        level = {s}
        while True:
            valid = list(filter(isValid, level)) # python2返回列表，python3返回filter类
            if valid:
                return valid
            level = {s[:i] + s[i+1:] for s in level for i in range(len(s))}