leetcode 301. Remove Invalid Parentheses BFS遍历得到所有合法的括号字符串 + 很棒的做法

布满荆棘的人生 2022-06-06 23:06 129阅读 0赞

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广度优先遍历即可。

我是在网上看到这道题的教程，发现做法真的很棒，还有一种DFS+回溯的做法，这个也很不错，但是看不懂，所以这里我选择了BFS的做法。

**需要注意的是判断括号有效性的做法值得学习。**

注意这里的**find标志变量**，这个是必须要有的，因为一到找到合法的表达式的时候就意味着对于接下来的子串的处理就是不必要的了，这个其实只是做BFS层遍历的第一层，假如不添加find标志标量，他会做下一层的遍历，这个就不是我们所要的结果了

建议和[leetcode 20. Valid Parentheses][] 和 [leetcode 678. Valid Parenthesis String 有效括号的判断][leetcode 678. Valid Parenthesis String] 和[leetcode 32. Longest Valid Parentheses 最长有效括号长度][leetcode 32. Longest Valid Parentheses] 一起学习

代码如下：

import java.util.ArrayList;
    import java.util.HashSet;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Queue;
    import java.util.Set;
    
    /*
     * 类似广度优先遍历的做法
     * 还有一个DFS的做法，但是看不懂
     * 
     * 如果是要求的到所有的合法的子串，那么
     * */
    class Solution 
    {
        public List<String> removeInvalidParentheses(String s)
        {
            List<String> res=new ArrayList<>();
            if(s==null)
                return res;
    
            Set<String> visit=new HashSet<>();
            Queue<String> queue=new LinkedList<>();
            queue.add(s);
            visit.add(s);
    
            boolean found=false;
            while(queue.isEmpty()==false)
            {
                String top=queue.poll();
                if(isVaild(top))
                {
                    res.add(top);
                    found=true;
                }
                if(found)
                    continue;
                for(int i=0;i<top.length();i++)
                {
                    if(top.charAt(i)=='(' || top.charAt(i)==')')
                    {
                        String one=top.substring(0,i)+top.substring(i+1);
                        if(visit.contains(one)==false)
                        {
                            queue.add(one);
                            visit.add(one);
                        }
                    }
                }
            }   
            return res;     
        }
    
        public boolean isVaild(String s) 
        {
            int count=0;
            for(int i=0;i<s.length();i++)
            {
                if(s.charAt(i)=='(')
                    count++;
                else if(s.charAt(i)==')')
                    count--;
                if(count<0)
                    return false;
            }
            return count==0;
        }
    
        /*
         * 获取所有的合法的子串
         * */
        public List<String> getAllValidParentheses(String s)
        {
            List<String> res=new ArrayList<>();
            if(s==null)
                return res;
    
            Set<String> visit=new HashSet<>();
            Queue<String> queue=new LinkedList<>();
            queue.add(s);
            visit.add(s);
    
            while(queue.isEmpty()==false)
            {
                String top=queue.poll();
                if(isVaild(top))
                    res.add(top);
                else
                {
                    for(int i=0;i<top.length();i++)
                    {
                        if(top.charAt(i)=='(' || top.charAt(i)==')')
                        {
                            String one=top.substring(0,i)+top.substring(i+1);
                            if(visit.contains(one)==false)
                            {
                                queue.add(one);
                                visit.add(one);
                            }
                        }
                    }
                }
            }   
            return res;     
        }
    }

下面是C++的做法，就是BFS遍历所有可能的情况，然后逐个处理即可，

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    
    using namespace std;
    
    class Solution 
    {
    public:
        vector<string> res;
        vector<string> removeInvalidParentheses(string s) 
        {
            set<string> visit;
            queue<string> que;
            que.push(s);
            visit.insert(s);
            bool find = false;
            while (que.empty() == false)
            {
                string top = que.front();
                que.pop();
                if (isValid(top))
                {
                    res.push_back(top);
                    find = true;
                }
                if (find == true)
                    continue;
                else
                {
                    for (int i = 0; i < top.length(); i++)
                    {
                        if (top[i] == '(' || top[i] == ')')
                        {
                            string tt = top.substr(0, i) + top.substr(i + 1);
                            if (visit.find(tt) == visit.end())
                            {
                                que.push(tt);
                                visit.insert(tt);
                            }
                        }
                    }
                }
            }
            return res;
        }
    
        bool isValid(string a)
        {
            int count = 0;
            for (char c : a)
            {
                if (c == '(')
                    count++;
                else if (c == ')')
                    count--;
                if (count < 0)
                    return false;
            }
            return count == 0 ? true : false;
        }
    };

[leetcode 20. Valid Parentheses]: http://blog.csdn.net/jackzhang_123/article/details/77748997
[leetcode 678. Valid Parenthesis String]: http://blog.csdn.net/jackzhang_123/article/details/78879862
[leetcode 32. Longest Valid Parentheses]: http://blog.csdn.net/jackzhang_123/article/details/77801969