1190. Reverse Substrings Between Each Pair of Parentheses

🟠   🔖  栈 字符串  🔗 LeetCode

题目

You are given a string s that consists of lower case English letters and brackets.

Reverse the strings in each pair of matching parentheses, starting from the innermost one.

Your result should not contain any brackets.

Example 1:

Input: s = "(abcd)"

Output: "dcba"

Example 2:

Input: s = "(u(love)i)"

Output: "iloveu"

Explanation: The substring "love" is reversed first, then the whole string is reversed.

Example 3:

Input: s = "(ed(et(oc))el)"

Output: "leetcode"

Explanation: First, we reverse the substring "oc", then "etco", and finally, the whole string.

Constraints:

• 1 <= s.length <= 2000
• s only contains lower case English characters and parentheses.
• It is guaranteed that all parentheses are balanced.

题目大意

给出一个字符串  s（仅含有小写英文字母和括号）。请你按照从括号内到外的顺序，逐层反转每对匹配括号中的字符串，并返回最终的结果。注意，您的结果中 不应 包含任何括号。

解题思路

对于括号序列相关的题目，通用的解法是使用递归或栈。本题中使用栈解决。

从左到右遍历该字符串，使用字符串 str 记录当前层所遍历到的小写英文字母。对于当前遍历的字符：

• 如果是左括号，将 str 插入到栈中，并将 str 置为空，进入下一层；
• 如果是右括号，则说明遍历完了当前层，需要将 str 反转，返回给上一层。具体地，将栈顶字符串弹出，然后将反转后的 str 拼接到栈顶字符串末尾，将结果赋值给 str。
• 如果是小写英文字母，将其加到 str 末尾。

仅在遇到右括号时才进行字符串处理，这样可以保证是按照从括号内到外的顺序处理字符串。

代码

/**
 * @param {string} s
 * @return {string}
 */
var reverseParentheses = function (s) {
  let stack = [];
  let str = "";
  for (let i = 0; i < s.length; i++) {
    if (s[i] === "(") {
      stack.push(str);
      str = "";
    } else if (s[i] === ")") {
      str = stack.pop() + str.split("").reverse().join("");
    } else {
      str += s[i];
    }
  }
  return str;
};