leetcode 22. Generate Parentheses DFS深度优先遍历

缺乏、安全感 2022-06-09 08:07 190阅读 0赞

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

\[  
“((()))”,  
“(()())”,  
“(())()”,  
“()(())”,  
“()()()”  
\]

这道题的目的是生成所有的可能的**有效的**配对的括号，这个就是DFS递归遍历即可实现，也可以使用栈实现，不说了，直接上代码：

import java.util.ArrayList;
    import java.util.List;
    
    /*
     * 递归遍历实现
     * */
    public class Solution 
    {
        Character []record;
        List<String> resList=new ArrayList<String>();
    
        public List<String> generateParenthesis(int n) 
        {
            record=new Character[2*n];
            getAll(0,n,n);
            return resList;
        }
    
        public void getAll(int k, int left, int right) 
        {
            if(left==0 && right==0)
            {
                StringBuilder builder=new StringBuilder();
                for(int i=0;i<record.length;i++)
                    builder.append(record[i]);
                resList.add(builder.toString());
            }else 
            {
                if(left>0)
                {
                    record[k]='(';
                    getAll(k+1, left-1, right);
                }
    
                if(left<right)
                {
                    record[k]=')';
                    getAll(k+1, left, right-1);
                }
            }
        }
    
        public static void main(String[] args)
        {
            Solution solution=new Solution();
            System.out.println(solution.generateParenthesis(3));
        }
    }

C++的做法如下，就是一个简单的DFS深度优先遍历。

代码如下：

#include <iostream>
    #include <vector>
    #include <string>
    
    using namespace std;
    
    class Solution 
    {
    public:
        vector<string> res;
        vector<string> generateParenthesis(int n) 
        {
            getByDFS(n, n,"");
            return res;
        }
    
        void getByDFS(int in, int out,string a)
        {
            if (in==0 && out==0)
            {
                string one = a;
                res.push_back(one);
            }
            else
            {
                if (in > 0)
                    getByDFS(in - 1, out, a+"(");
                if(in < out)
                    getByDFS(in , out-1, a + ")");
            }
        }
    };