LeetCode Remove Invalid Parentheses-白红宇

LeetCode Remove Invalid Parentheses

阅读量：5046 次

发布时间：2019-06-12

本文共 1381 字，大约阅读时间需要 4 分钟。

原题链接在这里：

题目：

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())()"]")(" -> [""]

题解：

题目要求减少最小个数的非法括号，要求最小，就想到BFS.

Queue 里加入原来的string s, 循环中从queue中poll出来一个string. 每次减掉一个括号，若是合法了就加到res中，同时停止继续enqueue, 只把queue中现有的一个level检查了就好。

若是没遇到合法的，就把str从头到尾减掉一个括号放回到queue中。

检查是否合法用isValid. 这种写法不需要stack, 节省了空间。

同时使用Set 来记录已经检查过的string, 检查过就不需要再次检查。

Time Complexity: O(n^2). n = s.length(). Space: O(n).

AC Java:

1 public class Solution { 2     public List
     
       removeInvalidParentheses(String s) { 3         List
      
        res = new ArrayList
       
        (); 4         if(s == null){ 5             return res; 6         } 7          8         LinkedList
        
          que = new LinkedList
         
          (); 9         HashSet
          
            visited = new HashSet
           
            (); //存储已经检查过的string, 没有必要重复检查10 que.add(s);11 visited.add(s);12 boolean found = false; //标签，检查是否找到了valid parentheses13 14 while(!que.isEmpty()){15 String str = que.poll();16 if(isValid(str)){17 res.add(str);18 found = true;19 }20 if(found){ //已经找到，就在本level中找剩下的就好了21 continue;22 }23 for(int i = 0; i