Description
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:
输入: "()())()" 输出: ["()()()", "(())()"]
示例 2:
输入: "(a)())()" 输出: ["(a)()()", "(a())()"]
示例 3:
输入: ")(" 输出: [""]
思路
- 深度优先搜索.
- 对于一个合法括号，在任意一个不是最后的位置，当前位置（包括）前面的左括号个数一定是大于等于右括号个数，此为我们判断一个字符串是否是合法字符串的条件.
- 我们首先获取需要去掉多少个左括号和去掉多少个右括号，然后我我们使用深度优先搜索，递归的先去左括号，再去右括号.
# -*- coding: utf-8 -*- # @Author: 何睿 # @Create Date: 2019-02-10 15:47:49 # @Last Modified by: 何睿 # @Last Modified time: 2019-02-10 17:57:38 class Solution: def removeInvalidParentheses(self, s: 'str') -> 'List[str]': # 如果为空，返回空字符串 if not s: return [""] # 统计非法的左右括号的个数 left, right = 0, 0 for _s in s: # 如果是左括号，left自增一次 if _s == "(": left += 1 # 如果没有非法的左括号，并且当前是右括号，right自增一次 if left == 0 and _s == ")": right += 1 # 否则如果当前是右括号，我们让当前的右括号和一个左括号匹配 # left自减一次 elif _s == ")": left -= 1 res = [] self.__dfs(s, 0, left, right, res) return res def __dfs(self, s, start, left, right, res): # 递归结束条件 if not left and not right and self.__valid(s): res.append(s) return for i in range(start, len(s)): # 避免重复 if i != start and s[i] == s[i - 1]: continue if s[i] == "(" or s[i] == ")": # 删除字符 current = s[0:i] + s[i + 1:] # 先删除右括号 if right > 0: self.__dfs(current, i, left, right - 1, res) # 再删除左括号 elif left > 0: self.__dfs(current, i, left - 1, right, res) return def __valid(self, s): # 统计有效的括号个数 # 只要不到最后一个位置，左括号个数一定大于右括号的个数 # 最后一个位置左右括号的个数相等 count = 0 for _s in s: # 遇到左括号，count加一 if _s == "(": count += 1 # 遇到右括号，count减一 if _s == ")": count -= 1 # 如果count小于0，说明当前位置一定没有足够的左括号 # 和右括号进行匹配，返回False if count < 0: return False return count == 0
源代码文件在这里.
