本文正在参加「Java主题月 – Java 刷题打卡」，详情查看活动链接

题目描述

给出一个字符串 s（仅含有小写英文字母和括号）。

请你按照从括号内到外的顺序，逐层反转每对匹配括号中的字符串，并返回最终的结果。

注意，您的结果中不应包含任何括号。

示例 1：

输入：s = "(abcd)"
输出："dcba"

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-substrings-between-each-pair-of-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
复制代码

思路分析

认真理解题目，这是一个括号问题，面对括号处理问题，一般采用栈这种数据结构，来记录数据。
栈这种数据结构，具有后进先出（last in first out）的性质。在 Java 中，我常常使用 Deque 来实现 Stack的功能。 Deque 是双端队列，使用起来更加方便。
代码实现的思路就是先找到最里层的括号，然后进行反转，逐层处理。

AC代码

public class DayCode {
    public static void main(String[] args) {
        String s = "(u(love)i)";
        String ans = new DayCode().reverseParentheses(s);
        System.out.println(ans);
        String ans1 = new DayCode().reverseParentheses1(s);
        System.out.println(ans1);
    }

    /**
     * 
     * @param s
     * @return
     */
    public String reverseParentheses(String s) {
        StringBuilder ans = new StringBuilder();
        Deque<Character> deque = new ArrayDeque<>();
        for (char ch : s.toCharArray()) {
            if (ch == ')') {
                Deque<Character> temp = new ArrayDeque<>();
                while (deque.peekLast() != '(') {
                    temp.offer(deque.pollLast());
                }
                if (deque.peekLast() == '(') {
                    deque.pollLast();
                }
                while (!temp.isEmpty()) {
                    deque.offer(temp.poll());
                }
            } else {
                deque.offer(ch);
            }
        }

        while (!deque.isEmpty()) {
            ans.append(deque.poll());
        }
        return ans.toString();
    }


    /**
     * 
     * @param s
     * @return
     */
    public String reverseParentheses1(String s) {
        StringBuffer ans = new StringBuffer();
        Deque<String> deque = new ArrayDeque<>();
        for (char ch : s.toCharArray()) {
            if (ch == '(') {
                deque.offer(ans.toString());
                ans.setLength(0);
            } else if (ch == ')') {
                ans.reverse();
                ans.insert(0, deque.removeLast());
            } else {
                ans.append(ch);
            }
        }

        return ans.toString();
    }
}
复制代码

总结

上述代码的时间复杂度是 O(n * n), 空间复杂度是 O(n)。
当我们对字符串进行频繁修改的时候，一般使用 StringBuffer 或者 StringBuilder 类。
和 String 类不同的是，StringBuffer 和 StringBuilder 类的对象能够被多次的修改，并且不产生新的未使用对象。具体实现可以从代码层面看一下。

StringBuffer 核心代码如下：

 public final class StringBuffer
    extends AbstractStringBuilder
    implements java.io.Serializable, CharSequence
{
    /**
     * A cache of the last value returned by toString. Cleared
     * whenever the StringBuffer is modified.
     */
    private transient char[] toStringCache;
    
    /**
     * Constructs a string buffer with no characters in it and an
     * initial capacity of 16 characters.
     */
    public StringBuffer() {
        super(16);
    }
    
    @Override
    public synchronized StringBuffer append(char c) {
        toStringCache = null;
        super.append(c);
        return this;
    }
    
    @Override
    public synchronized String toString() {
        if (toStringCache == null) {
            toStringCache = Arrays.copyOfRange(value, 0, count);
        }
        return new String(toStringCache, true);
    }
}
复制代码

StringBuilder 核心代码如下：

public final class StringBuilder
    extends AbstractStringBuilder
    implements java.io.Serializable, CharSequence
{
    /**
     * Constructs a string builder with no characters in it and an
     * initial capacity of 16 characters.
     */
    public StringBuilder() {
        super(16);
    }
    
    @Override
    public StringBuilder append(String str) {
        super.append(str);
        return this;
    }
    
    @Override
    public String toString() {
        // Create a copy, don't share the array
        return new String(value, 0, count);
    }
}
复制代码