反转每对括号间的子串
题面
leetcode题目
给出一个字符串 s（仅含有小写英文字母和括号）。
请你按照从括号内到外的顺序，逐层反转每对匹配括号中的字符串，并返回最终的结果。
注意，您的结果中 不应 包含任何括号。
example
example 1
输入：s = "(abcd)" 输出："dcba"
example 2
输入：s = "(u(love)i)" 输出："iloveu"
example 3
输入：s = "(ed(et(oc))el)" 输出："leetcode"
题解
总体思路
括号匹配相关的问题，首先想想是不是能用栈解决，考虑一个最古朴的括号匹配问题，我们可以匹配出()一对括号内的内容，如果要反转内容只需要顺序入栈即可。
于是我们可以考虑维护一个栈\(stk\)，顺序遍历字符串，如果发现当前遍历到右括号位置，则把栈中到左括号位置中间的所有字符翻转一遍(出栈再入栈即可)。
更为仔细的考虑这道题，我们可以按照这种思路来写，维护\(stk\)表示当前在括号内的字符 , 维护 \(vec\)表示当前需要翻转的子串，那么我们在遍历字符串的时候，就存在两种可能:
- 如果当前字符\(c\)满足\(c=)\)，那么开始对\(stk\)进行出栈操作，将出栈的元素放入\(vec\)的最后一个位置，直到出栈的元素为\((\)为止。出栈结束后，将\(vec\)中的元素顺序重新入栈\(stk\)。
- 如果当前字符\(c\)不满足\(c=)\)，那么直接将当前字符入栈\(stk\)即可。
实际上在这个时候我们还需要对栈中元素再进行一次反转才能得到最终的结果，为了方便我们可以在字符串的最外层加上两对()，因为两次翻转后的结果是与翻转前一致的，所以结果不变，这样的话，我们就不需要再在最后对\(stk\)进行一次翻转，可以直接从\(vec\)中读出结果了。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
| #include <iostream>
#include <vector>
#include <stack>
#include <string>
using namespace std;
#define _NDEBUG
class Solution
{
public:
string reverseParentheses(string s)
{
s = "((" + s + "))";
stack<char> stk;
vector<char> tmp;
for (int i = 0; i < s.length(); i++)
{
char c = s[i];
#ifdef _DEBUG
cout << "c: " << c << endl;
#endif
if (c == ')')
{
tmp.clear();
while (true)
{
char top = stk.top();
stk.pop();
#ifdef _DEBUG
cout << "top: " << top << endl;
#endif
if (top == '(')
{
for (auto iter = tmp.begin(); iter != tmp.end(); iter++)
{
#ifdef _DEBUG
cout << "iter: " << *iter << endl;
#endif
stk.push(*iter);
}
break;
}
else
{
tmp.push_back(top);
}
}
}
else
{
stk.push(c);
}
}
string ret = "";
for (auto i = tmp.begin(); i != tmp.end(); i++)
{
ret += *i;
}
return ret;
}
};
int main()
{
Solution s;
string t1 = "(abcd)";
string t2 = "(u(love)i)";
string t3 = "(ed(et(oc))el)";
string t4 = "a(bcdefghijkl(mno)p)q";
string t5 = "a(bcdefghijkl(mno)p)q";
cout << s.reverseParentheses(t1) << endl;
cout << s.reverseParentheses(t2) << endl;
cout << s.reverseParentheses(t3) << endl;
cout << s.reverseParentheses(t4) << endl;
cout << s.reverseParentheses(t5) << endl;
return 0;
}
|