【LeetCode】反转每对括号间的子串 Java 题解

关注

发布于: 2021 年 06 月 05 日

题目描述

给出一个字符串 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);    }}

复制代码

由代码实现可知： StringBuffer 使用 synchronized 关键字修饰，是线程安全。StringBuilder 不是线程安全，效率更高！
坚持每日一题，加油！

发布于: 2021 年 06 月 05 日阅读数: 6

原文链接:【http://xie.infoq.cn/article/025ca6de96c18c1e479dd5c70】。文章转载请联系作者。

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

【LeetCode】反转每对括号间的子串 Java 题解

题目描述

思路分析

AC 代码

总结

HQ数字卡

评论