首页 > 代码库 > [LeetCode系列]括号生成问题

[LeetCode系列]括号生成问题

2024-07-17 14:51:27   218人阅读

给定n, 返回所有匹配的n对括号的可能形式. 如

给定 n = 3, 一个解集是:

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

本题解法的思路是

使用栈seq保存经历的字符串状态;

使用栈valid保存对应的字符串中有效的括号对个数;

当seq不为空时(即回溯未结束):

　　当前的字符串和其中有效的括号对个数分别出栈;

　　1. 如果字符串长度等于待求解的长度, 则将其加答案中;

　　2. 如果字符串长度-有效括号对数小于最大括号对个数, 说明可以增加一个 "("; [有效括号对数代表已经放置的")", 这个差值代表已经放置的"("个数]

　　3. 如果字符串长度大于成对的括号数, 说明需要加一个 ")", 并且有效括号对需要增加1; [说明有未配对的"("]

 1 class Solution { 2 public: 3     vector<string> generateParenthesis(int n) { 4         if (n == 0) return vector<string> (0); 5         stack<string> seq; 6         stack<int> valid; 7         vector<string> ans; 8          9         seq.push("(");10         valid.push(0);11         while (!seq.empty()) {12             string s = seq.top(); seq.pop();13             int v = valid.top(); valid.pop();14             if (s.length() == 2 * n) {15                 ans.push_back(s);16                 continue;17             }18             if (s.length() - v < n) {19                 seq.push(s + "(");20                 valid.push(v);21             }22             if (v * 2 < s.length()) {23                 seq.push(s + ")");24                 valid.push(v+1);25             }26         }27         return ans;28     }29     30 };

 


联系
我们