LeetCode 301. Remove Invalid Parentheses

原题链接在这里：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 ).

Examples:

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

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

")(" -> [""]

题解：

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

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

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

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

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

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

AC Java:

 public class Solution {

     public List<String> removeInvalidParentheses(String s) {

         List<String> res = new ArrayList<String>();

         if(s == null){

             return res;

         }

         LinkedList<String> que = new LinkedList<String>();

         HashSet<String> visited = new HashSet<String>(); //存储已经检查过的string, 没有必要重复检查

         que.add(s);

         visited.add(s);

         boolean found = false; //标签，检查是否找到了valid parentheses

         while(!que.isEmpty()){

             String str = que.poll();

             if(isValid(str)){

                 res.add(str);

                 found = true;

             }

             if(found){      //已经找到，就在本level中找剩下的就好了

                 continue;

             }

             for(int i = 0; i<str.length(); i++){

                 if(str.charAt(i) != '(' && str.charAt(i) != ')'){

                     continue;

                 }

                 String newStr = str.substring(0,i) + str.substring(i+1);

                 if(!visited.contains(newStr)){

                     que.add(newStr);

                     visited.add(newStr);

                 }

             }

         }

         return res;

     }

     private boolean isValid(String s){

         int count = 0;

         for(int i = 0; i<s.length(); i++){

             if(s.charAt(i) == '('){

                 count++;

             }

             if(s.charAt(i) == ')'){

                 if(count == 0){

                     return false;

                 }else{

                     count--;

                 }

             }

         }

         return count == 0;

     }

 }

类似Minimum Remove to Make Valid Parentheses.

巴特西

LeetCode 301. Remove Invalid Parentheses

最新文章

热门文章