C++刷leetcode（1021. 删除最外层的括号）【深度优先搜索】

糖逗

题目描述：

1. 有效括号字符串为空 ("")、"(" + A + ")" 或 A + B，其中 A 和 B 都是有效的括号字符串，+ 代表字符串的连接。例如，""，"()"，"(())()" 和 "(()(()))" 都是有效的括号字符串。
   
2. 
   
3. 如果有效字符串 S 非空，且不存在将其拆分为 S = A+B 的方法，我们称其为原语（primitive），其中 A 和 B 都是非空有效括号字符串。
   
4. 
   
5. 给出一个非空有效字符串 S，考虑将其进行原语化分解，使得：S = P_1 + P_2 + ... + P_k，其中 P_i 是有效括号字符串原语。
   
6. 
   
7. 对 S 进行原语化分解，删除分解中每个原语字符串的最外层括号，返回 S 。
   
8. 
   
9.  
   
10. 
    
11. 示例 1：
    
12. 
    
13. 输入："(()())(())"
    
14. 输出："()()()"
    
15. 解释：
    
16. 输入字符串为 "(()())(())"，原语化分解得到 "(()())" + "(())"，
    
17. 删除每个部分中的最外层括号后得到 "()()" + "()" = "()()()"。
    
18. 示例 2：
    
19. 
    
20. 输入："(()())(())(()(()))"
    
21. 输出："()()()()(())"
    
22. 解释：
    
23. 输入字符串为 "(()())(())(()(()))"，原语化分解得到 "(()())" + "(())" + "(()(()))"，
    
24. 删除每个部分中的最外层括号后得到 "()()" + "()" + "()(())" = "()()()()(())"。
    
25. 示例 3：
    
26. 
    
27. 输入："()()"
    
28. 输出：""
    
29. 解释：
    
30. 输入字符串为 "()()"，原语化分解得到 "()" + "()"，
    
31. 删除每个部分中的最外层括号后得到 "" + "" = ""。
    
32.  
    
33. 
    
34. 提示：
    
35. 
    
36. S.length <= 10000
    
37. S[i] 为&#160;"(" 或&#160;")"
    
38. S 是一个有效括号字符串
    
39. 
    
40. 来源：力扣（LeetCode）
    
41. 链接：https://leetcode-cn.com/problems/remove-outermost-parentheses
    
42. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. #include <iostream>
   
2. #include <vector>
   
3. #include <string>
   
4. 
   
5. using namespace std;
   
6. 
   
7. bool valid(string temp){
   
8.     int count = 0;
   
9.     for(auto cha : temp){
   
10.         if(count < 0) return false;
    
11.         if(cha =='(') count ++;
    
12.         if(cha == ')') count--;
    
13. 
    
14.     }
    
15.     return count == 0;
    
16. }
    
17. void dfs(string S, string& res, int start, string temp){
    
18.     if(start > S.size()) return;
    
19.     if(valid(temp)){
    
20.         if(temp.size() > 2){
    
21.             res += temp.substr(1, temp.size()-2);
    
22.         }
    
23.         temp = "";
    
24.     }
    
25.     temp += S[start];
    
26.     dfs(S, res, start + 1, temp);
    
27. }
    
28. string removeOuterParentheses(string S) {
    
29.     string res;
    
30.     dfs(S, res, 0, "");
    
31.     return res;
    
32. }
    
33. 
    
34. int main(void){
    
35.         string input;
    
36.         cin >> input;
    
37.         cout << removeOuterParentheses(input) << endl;
    
38.         return 0;
    
39. }

复制代码

糖逗

递归思想