Leetcode每日一题 —— 1190. 反转每对括号间的子串

开发调优
,
1

思路

一开始想着不用递归和字符串，借助括号的首尾记录和字符数组来构造字符串，但是发现反倒是更复杂了。最终还是回归简单，按深度直接DFS。
遇到’(‘直接交给下一层DFS，返回的时候位置跳到下一层后面，直到遇到当前层’)'为止。

代码

class Solution {
    private char[] chars;
    public String reverseParentheses(String s) {
        chars = s.toCharArray();
        Pair<Integer, StringBuilder> pair = dfs(0);
        return pair.getValue().toString();
    }
    private Pair<Integer, StringBuilder> dfs(int idx) {
        StringBuilder ans = new StringBuilder();
        while (idx < chars.length && chars[idx] != ')') {
            if (chars[idx] == '(') {
                Pair<Integer, StringBuilder> pair = dfs(idx + 1);
                idx = pair.getKey();
                ans.append(pair.getValue().reverse());
            } else {
                ans.append(chars[idx]);
            }
            idx++;
        }
        return new Pair<>(idx, ans);
    }
}
1 个赞
2

典型的栈应用题。

class Solution {
public:
    string reverseParentheses(string s) {
        // 可以维护左括号的位置
        // 每次遇到右括号就弹出对应的左括号下标，把这之间的字符串反转
        stack<int> stk;
        for(int i=0;i<s.size();i++){
            if(s[i]=='('){
                stk.emplace(i);
            }else if(s[i]==')'){
                reverse(s.begin()+stk.top()+1,s.begin()+i);
                stk.pop();
            }
        }
        // 在结果中剥离括号
        string res;
        for(char c:s){
            if(c!='('&&c!=')'){
                res.push_back(c);
            }
        }
        return res;
    }
};