class Solution {
public:
string reverseParentheses(string s) {
}
};
1190. 反转每对括号间的子串
给出一个字符串 s（仅含有小写英文字母和括号）。
请你按照从括号内到外的顺序，逐层反转每对匹配括号中的字符串，并返回最终的结果。
注意，您的结果中 不应 包含任何括号。
示例 1：
输入：s = "(abcd)" 输出："dcba"
示例 2：
输入：s = "(u(love)i)" 输出："iloveu" 解释：先反转子字符串 "love" ，然后反转整个字符串。
示例 3：
输入：s = "(ed(et(oc))el)" 输出："leetcode" 解释：先反转子字符串 "oc" ，接着反转 "etco" ，然后反转整个字符串。
示例 4：
输入：s = "a(bcdefghijkl(mno)p)q" 输出："apmnolkjihgfedcbq"
提示：
0 <= s.length <= 2000s 中只有小写英文字母和括号原站题解
python3 解法, 执行用时: 44 ms, 内存消耗: 15.1 MB, 提交时间: 2022-11-27 12:39:24
class Solution:
def reverseParentheses(self, s: str) -> str:
stack = []
n = len(s)
i = 0
while i < n:
if s[i] != ')':
stack.append(s[i])
i +=1
else:
result = ''
cur = stack.pop()
while cur!= '(':
result += cur
cur = stack.pop()
for char in result:
stack.append(char)
i +=1
return ''.join(stack)
javascript 解法, 执行用时: 60 ms, 内存消耗: 41.6 MB, 提交时间: 2022-11-27 12:38:44
/**
* @param {string} s
* @return {string}
*/
var reverseParentheses = function(s) {
const stk = [];
let str = '';
for (const ch of s) {
if (ch === '(') {
stk.push(str);
str = '';
} else if (ch === ')') {
str = str.split("").reverse().join("");
str = stk[stk.length - 1] + str;
stk.pop();
} else {
str += ch;
}
}
return str;
};
javascript 解法, 执行用时: 52 ms, 内存消耗: 41.1 MB, 提交时间: 2022-11-27 12:38:27
/**
* @param {string} s
* @return {string}
*/
var reverseParentheses = function(s) {
const n = s.length;
const pair = new Array(n).fill(0);
const stack = [];
for (let i = 0; i < n; i++) {
if (s[i] === '(') {
stack.push(i);
} else if (s[i] == ')') {
const j = stack.pop();
pair[i] = j;
pair[j] = i;
}
}
const sb = [];
let index = 0, step = 1;
while (index < n) {
if (s[index] === '(' || s[index] === ')') {
index = pair[index];
step = -step;
} else {
sb.push(s[index]);
}
index += step;
}
return sb.join('');
};
golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2022-11-27 12:38:13
func reverseParentheses(s string) string {
n := len(s)
pair := make([]int, n)
stack := []int{}
for i, b := range s {
if b == '(' {
stack = append(stack, i)
} else if b == ')' {
j := stack[len(stack)-1]
stack = stack[:len(stack)-1]
pair[i], pair[j] = j, i
}
}
ans := []byte{}
for i, step := 0, 1; i < n; i += step {
if s[i] == '(' || s[i] == ')' {
i = pair[i]
step = -step
} else {
ans = append(ans, s[i])
}
}
return string(ans)
}
golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2022-11-27 12:37:57
func reverseParentheses(s string) string {
stack := [][]byte{}
str := []byte{}
for i := range s {
if s[i] == '(' {
stack = append(stack, str)
str = []byte{}
} else if s[i] == ')' {
for j, n := 0, len(str); j < n/2; j++ {
str[j], str[n-1-j] = str[n-1-j], str[j]
}
str = append(stack[len(stack)-1], str...)
stack = stack[:len(stack)-1]
} else {
str = append(str, s[i])
}
}
return string(str)
}