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树的扩展(因为要去除最少括号,所以即使有其他的结果,也一定在同一层)

更简洁的写法

 

方法二: DFS

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

 

 

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode Remove Invalid Parentheses
本文地址:https://www.hrwhisper.me/leetcode-remove-invalid-parentheses/

打赏一杯咖啡钱呗

Leetcode , , . permalink.

One thought on “leetcode Remove Invalid Parentheses

Leave a Reply

Your email address will not be published. Required fields are marked *