题目形容

这是 LeetCode 上的 1190. 反转每对括号间的子串 ，难度为 中等。

Tag : 「双端队列」、「栈」

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

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

留神，您的后果中 不应 蕴含任何括号。

示例 1：

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

示例 2：

输出：s = "(u(love)i)"输入："iloveu"

示例 3：

输出：s = "(ed(et(oc))el)"输入："leetcode"

示例 4：

输出：s = "a(bcdefghijkl(mno)p)q"输入："apmnolkjihgfedcbq"

提醒：

  • $0 <= s.length <= 2000$
  • s 中只有小写英文字母和括号
  • 咱们确保所有括号都是成对呈现的

双端队列

依据题意，咱们能够设计如下解决流程：

  • 从前往后遍历字符串，将不是 ) 的字符串从「尾部」放入队列中
  • 当遇到 ) 时，从队列「尾部」取出字符串，直到遇到 ( 为止，并对取出字符串进行翻转
  • 将翻转实现后字符串从新从「尾部」放入队列
  • 循环上述过程，直到原字符串全副进去实现
  • 从队列「头部」开始取字符，失去最终的答案

能够发现，上述过程须要用到双端队列（或者栈，应用栈的话，须要在最初一步对取出字符串再进行一次翻转）。

在 Java 中，双端队列能够应用自带的 ArrayDeque， 也能够间接应用数组进行模仿。

代码（应用 ArrayDeque ）：

class Solution {    public String reverseParentheses(String s) {        int n = s.length();        char[] cs = s.toCharArray();        Deque<Character> d = new ArrayDeque<>();        for (int i = 0; i < n; i++) {            char c = cs[i];            if (c == ')') {                StringBuilder path = new StringBuilder();                while (!d.isEmpty()) {                    if (d.peekLast() != '(') {                        path.append(d.pollLast());                    } else {                        d.pollLast();                        for (int j = 0; j < path.length(); j++) d.addLast(path.charAt(j));                        break;                    }                }            } else {                d.addLast(c);            }        }        StringBuilder sb = new StringBuilder();        while (!d.isEmpty()) sb.append(d.pollFirst());        return sb.toString();    }}

代码（数组模仿双端队列）：

class Solution {    int N = 2010, he = 0, ta = 0;    char[] d = new char[N], path = new char[N];    public String reverseParentheses(String s) {        int n = s.length();        char[] cs = s.toCharArray();        for (int i = 0; i < n; i++) {            char c = cs[i];            if (c == ')') {                int idx = 0;                while (he < ta) {                    if (d[ta - 1] == '(' && --ta >= 0) {                        for (int j = 0; j < idx; j++) d[ta++] = path[j];                        break;                    } else {                        path[idx++] = d[--ta];                    }                }            } else {                d[ta++] = c;            }        }        StringBuilder sb = new StringBuilder();        while (he < ta) sb.append(d[he++]);        return sb.toString();    }}
  • 工夫复杂度：每个 ( 字符只会进出队列一次；) 字符串都不会进出队列，也只会被扫描一次；剖析的重点在于一般字符，能够发现每个一般字符进出队列的次数取决于其左边的 ) 的个数，最坏状况下每个字符左边全是右括号，因而复杂度能够当做 $O(n^2)$，但理论计算量必然取不满 $n^2$，将一般字符的反复弹出均摊到整个字符串处理过程，能够看作是每个字符串都被遍历常数次，复杂度为 $O(n)$
  • 空间复杂度：$O(n)$

最初

这是咱们「刷穿 LeetCode」系列文章的第 No.1190 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。

在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。

为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou... 。

在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。

更多更全更热门的「口试/面试」相干材料可拜访排版精美的 合集新基地

本文由mdnice多平台公布