每日题解:LeetCode 1190. 反转每对括号间的子串

Author Avatar
清水雅然君 08月 06,2020

题目地址

题目描述

给出一个字符串 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 中只有小写英文字母和括号
我们确保所有括号都是成对出现的

解法

class Solution {

  public String reverseParentheses(String s) {
        Stack<Integer> stack = new Stack<>();
        char[] temp = s.toCharArray();
        int len = s.length();
        for (int i = 0; i < len; i++) {
            if (temp[i] == '(') {
                stack.push(i);
            } else if (temp[i] == ')') {
                reverse(temp, stack.pop()+1, i-1);
            }
        }
        StringBuilder stringbuilder=new StringBuilder();
        for (char c : temp) {
            if (c != '('&& c != ')') {
                stringbuilder.append(c);
            }
        }
        return stringbuilder.toString();
    }

    public void reverse(char[] arr, int left, int right) {
        while (left<right) {
            char temp=arr[left];
            arr[left]=arr[right];
            arr[right]=temp;
            ++left;
            --right;
        }
    }
}

解题思路

(ed(et(oc))el)"为例子,按照题目的意思
1、 反转最里面的(oc)的字符,得到字符(ed(etco)el)
2、 然后反转ed(etco)外边的字符(edocteel)
3、 最后反转整个字符leetcode
栈顶元素记录(的下标,当遇到),反转()内的字符

  for (int i = 0; i < len; i++) {
  //记录下标
            if (temp[i] == '(') {
                stack.push(i);
            } else if (temp[i] == ')') {
            //反转字段
                reverse(temp, stack.pop()+1, i-1);
            }
        }

反转字符的方法

public void reverse(char[] arr, int left, int right) {
        while (left<right) {
            char temp=arr[left];
            arr[left]=arr[right];
            arr[right]=temp;
            ++left;
            --right;
        }
    }