在线时间:8:00-16:00
迪恩网络APP
随时随地掌握行业动态
扫描二维码
关注迪恩网络微信公众号
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 }
代码分析: 递归做法。
|
请发表评论