【Leetcode】22. Generate Parentheses总结

无情 阅读:342 2022-03-12 16:24:44 评论:0
本文章主要介绍了【Leetcode】22. Generate Parentheses,具有不错的的参考价值,希望对您有所帮助,如解说有误或未考虑完全的地方,请您留言指出,谢谢!

回溯法的应用

原题

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:

[ 
  "((()))", 
  "(()())", 
  "(())()", 
  "()(())", 
  "()()()" 
] 

题意是求n组括号的组合方式,要求能够组成合理的左右括号。

分析:

所谓合理的组合方式,应该是左右括号数量相等,在初始情况下应该先添加左括号,在递归过程中左括号数量大于等于右括号的数量,我们记录左右括号的数量和当前字符串,如果左括号数量小于n,则字符串可以添加一个左括号,左括号数量增加一,进入下一轮递归;如果右括号数量小于左括号数量,则字符串添加一个右括号,右括号数量加一后进入下一轮递归。

函数原型:

dfs(String currentString, int leftCount, int rightCount, int n); 

迭代的过程如下图所示:

代码:

import java.util.ArrayList; 
import java.util.List; 
 
/** 
 * Author: puyangsky 
 * Date: 17/4/27 
 * 方法:递归、回溯 
 */ 
public class L22GenerateParentheses { 
 
    private static List<String> list = new ArrayList<>(); 
 
    public static void dfs(List<String> list, String parenthesis, int left, int right, int count) { 
        if (parenthesis.length() == count * 2) {//达到最大长度,添加到结果中 
            list.add(parenthesis); 
            return; 
        } 
        //左括号仍然可以添加的情况 
        if (left < count) 
            dfs(list, parenthesis + "(", left + 1, right, count); 
 
		//右括号可以添加的情况 
        if (right < left) 
            dfs(list, parenthesis + ")", left, right + 1, count); 
    } 
 
    public static List<String> generateParenthesis(int n) { 
        dfs(list, "", 0, 0, n); 
        return list; 
    } 
 
 
    public static void main(String[] args) { 
        generateParenthesis(3); 
        for (String l : list) { 
            System.out.println(l); 
        } 
    } 
} 

结果输出:

((())) 
(()()) 
(())() 
()(()) 
()()()

标签:加密算法
声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

我的关注

全民解析

搜索
排行榜
关注我们