每日算法题—反转每对括号间的子串

题目描述

要求：按照从括号内到外的顺序，逐层反转每对匹配括号中的字符串，并返回最终的结果，且括号成对出现
输入：s = "(abcd)"
输出："dcba"

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

来源：https://leetcode-cn.com/problems/reverse-substrings-between-each-pair-of-parentheses/

思路

题目要求从内到外逐层反转，关键是要确定到达最里层括号的条件。
从左到右遍历字符串，当遇到第一个“)”时即可确定到达最里层括号，此时将最后一个左括号到第一个右括号的内容反转，重复这个过程直到结束

工具：栈、数组
逻辑：
从左到右遍历字符串并将字符入栈，当遇到第一个“)”时，依次出栈并将字符存入数组（此时数组中的字符顺序已经反转），当出栈时遇到第一个“(”时，再将数组中的内容依次入栈（完成一对括号内容的反转），继续遍历字符串并重复上述操作直到结束

代码实现

Kotlin：

fun reverseParentheses(s: String): String {
        val stack: Stack<Char> = Stack()
        val list: ArrayList<Char> = ArrayList()
        s.toCharArray().forEachIndexed { i, c ->
            if (c == ')') {
                while (stack.peek() != '(') {
                    list.add(stack.pop())
                }
                stack.pop()  //将遇到的‘(’出栈
                list.iterator().forEach {  //此时list中的字符已经反转，栈的特性，先进先出
                    stack.push(it)  
                }
                list.clear()  //清空list为下一次反转做准备
            } else {
                stack.push(c) 
            }
        }
        val sb = StringBuilder()
        stack.forEach { sb.append(it) }  //最后栈中的内容就是反转后的内容
        return sb.toString()
}

Java：

static String reverseParentheses(String s) {
        Stack<Character> stack = new Stack<>();
        ArrayList<Character> list = new ArrayList<>();
        for (int i = 0, l = s.toCharArray().length; i < l; i++) {
            char c = s.charAt(i);
            if (c == ')') {
                while (stack.peek() != '(') {
                    list.add(stack.pop());
                }
                stack.pop();
                for (char ch :list){
                    stack.push(ch);
                }
                list.clear();
            } else {
                stack.push(c);
            }
        }
        StringBuilder result = new StringBuilder();
        stack.forEach(result::append);
        return result.toString();
}