No.022：Generate Parentheses-白红宇的个人博客

No.022：Generate Parentheses

发布日期：2021-05-09 03:59:00 浏览次数：18 分类：博客文章

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

问题：

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:

[

"((()))",

"(()())",

"(())()",

"()(())",

"()()()"

]

官方难度：

Medium

翻译：

合并n个括号，生成所有n个括号组成的合理序列。

例子：

给定n=3，解集为

[

"((()))",

"(()())",

"(())()",

"()(())",

"()()()"

]

方法一：

初始的思想，考虑使用递归，每次优先获取n-1个括号所有情况下的集合，然后插入新的括号。

递归的终点是n=1，返回包含一个元素“()”的集合。

每次先加“(”，在第一个位置和一个“)”的下一个位置，插入左括号。

然后加右括号，从加入的左括号开始，统计左括号和右括号的个数，在左括号个数大于右括号个数的情况下，才可以加入右括号。

不难发现，虽然已经极力避免了，但是这种方法会出现很多的重复情况，所以需要一个Set集合去重，在递归结束之后，转化成List集合返回。

方法一的解题代码：

1     // 根据n-1的情况增加括号 2     public static List
     
       method(int n) { 3         List
      
        list = new ArrayList<>(getPharentheses(n)); 4         return list; 5     } 6  7     private static Set
       
         getPharentheses(int n) { 8         Set
        
          set = new HashSet<>(); 9         if (n == 1) {10             set.add("()");11         } else {12             Set
         
           last = getPharentheses(n - 1);13             for (String s : last) {14                 String s1 = "(" + s;15                 int l1 = 0;16                 int r1 = 0;17                 for (int j = 1; j < s1.length(); j++) {18                     if (s1.charAt(j) == '(') {19                         l1++;20                     } else {21                         r1++;22                     }23                     // 这里有重复的可能性24                     if (l1 > r1) {25                         set.add(s1.substring(0, j + 1) + ")" + s1.substring(j + 1));26                     }27                 }28                 // 先加左括号29                 for (int i = 1; i < s.length(); i++) {30                     if (s.charAt(i) == ')') {31                         String str = s.substring(0, i + 1) + "(" + s.substring(i + 1);32                         // 左右括号计数33                         int l = 0;34                         int r = 0;35                         for (int j = i + 1; j < str.length(); j++) {36                             if (str.charAt(j) == '(') {37                                 l++;38                             } else {39                                 r++;40                             }41                             // 这里有重复的可能性42                             if (l > r) {43                                 set.add(str.substring(0, j + 1) + ")" + str.substring(j + 1));44                             }45                         }46                     }47                 }48             }49         }50         return set;51     }

method

方法二：

显而易见，如果通过某种算法，没有重复的情况产生，那么方法的执行效率一定会快很多。

假设n=3。先加上所有的左括号，“(((”，那么右括号的可能性只有一个，那就是“((()))”。

然后回退一步，少加一个左括号，加上一个右括号，之后再加上这个左括号，会形成以下形式“(()())”。

后加的左括号再回退一步“(())()”。依次类推，直到这个左括号不能再加为止，回退至第一步，在一开始回退2个左括号，得到以下2种形式“()(())”和“()()()”。

发现回退的左括号为n时，结束。

解题的代码形式很简单，但是逻辑比较难捋通顺。

注意入参检查。

方法二的解题代码：

1     public static List
     
       generateParenthesis(int n) { 2         if (n < 1) { 3             throw new IllegalArgumentException("Input error"); 4         } 5         List
      
        list = new ArrayList<>(); 6         generate(n, n, "", list); 7         return list; 8     } 9 10     // 先加所有左括号，遍历所有可能性，然后回退一个左括号，依次类推11     private static void generate(int left, int right, String current, List
       
         list) {12         // 先加左括号13         if (left > 0) {14             generate(left - 1, right, current + "(", list);15         }16         if (right > 0 && right > left) {17             generate(left, right - 1, current + ")", list);18         }19         if (left == 0 && right == 0) {20             list.add(current);21         }22     }

generateParenthesis

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章