• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

LeetCodeOnlineJudge题目C#练习-GenerateParentheses

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

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:

"((()))", "(()())", "(())()", "()(())", "()()()"

 1         public static List<string> GenerateParenthesesDPOpt(int n)
 2         {
 3             List<HashSet<string>> ret = new List<HashSet<string>>();
 4             ret.Add(new HashSet<string>(){""});
 5 
 6             for (int i = 1; i <= n; i++)
 7             {
 8                 ret.Add(new HashSet<string>());
 9                 foreach (var s in ret[i - 1])
10                 {
11                     string temp = "()" + s;
12                     ret[i].Add(temp);
13 
14                     temp = s + "()";
15                     ret[i].Add(temp);
16 
17                     temp = "(" + s + ")";
18                     ret[i].Add(temp);
19 
20                     for (int j = 0; j < s.Length; j++) //Credit to ffengfrank, Thank you!
21                     {
22                         if (s[j] == '(')
23                         {
24                             temp = s.Insert(j + 1, "()");
25                             ret[i].Add(temp);
26                         }
27                     }
28                 }
29             }
30 
31             return ret[n].ToList();
32         }

 

代码分析:

  DP

n = 1 : ()

n = 2 : ()(), ()()重复, (())

n = 3 : ()()(), ()()()重复, (()()), ()(()), (())(), ((()))

......

利用HASHSET<string>减少时间复杂度。 每次比较的时间从O(n)到O(1)

感谢ffengfrank找到的bug,添加了20 ~ 27代码。

 

 1 public static List<string> GenerateParenthesesRecursive(int n)
 2         {
 3             string result = "";
 4             List<string> ret = new List<string>();
 5             GenerateParenthesesRecursive(n, n, result, ret);
 6             return ret;
 7         }
 8 
 9         public static void GenerateParenthesesRecursive(int left, int right, string result, List<string> ret)
10         {
11             if (left == 0 && right == 0)
12             {
13                 ret.Add(result);
14             }
15             else
16             {
17                 if (left > 0)
18                 {
19                     result += "(";
20                     GenerateParenthesesRecursive(left - 1, right, result, ret);
21                     result = result.Remove(result.Length - 1);
22                 }
23                 if (right > left)
24                 {
25                     result += ")";
26                     GenerateParenthesesRecursive(left, right - 1, result, ret);
27                     result = result.Remove(result.Length - 1);
28                 }
29             }
30         }

 

代码分析:

  递归做法。

 

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
c#判断一段代码运行所花费的时间发布时间:2022-07-14
下一篇:
UnityC#数据持久化与xml发布时间:2022-07-14
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap