X

LEETCODE 1190. Reverse Substrings Between Each Pair of Parentheses 解题思路分析

题目大意:

反转每对括号间的子串

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

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1190

解题思路分析:

原字符串包含多层括号嵌套,翻转顺序由内至外,很容易想到使用递归思路来解题。当我们看到正括号时,说明需要进入下一层的嵌套,这时将问题扔给递归子问题去解决。当遇到反括号时,说明本层嵌套结束,此时应该结束当前递归返回递归函数上一层。如果遇到的是小写字母,我们就将其按顺序拼接起来,在本层递归结束时反转后返回给上一层即可。因此每一层的递归函数大概是下面这样:

String helper(){
    String result = "小写字母" + "(" + "递归函数返回结果helper()" +")" + "小写字母";
    result.reverse();
    return result;
}

当递归结束时,所有的字符都会按条件反转,注意的是,最外层如果没有括号,那么最外层是不需要反转的。另外,这个结果中包含括号字符,应该在最后将其全部删除。

看下实现代码:

public String reverseParentheses(String s) {
    // 先递归反转所有字符
    String temp= helper(s, 0, 0).toString();
    // 删除所有括号字符
    StringBuilder sb = new StringBuilder();
    for(int i=0;i<temp.length();i++){
        if(temp.charAt(i)!=')' && temp.charAt(i)!='('){
            sb.append(temp.charAt(i));
        }
    }
    return sb.toString();
}
// 递归函数
// s为原字符串
// index为字符当前的下标
// level为括号嵌套深度,默认0为最外层无括号
public StringBuilder helper(String s, int index, int level){
    StringBuilder sb = new StringBuilder(); // 返回结果
    for(int i=index;i<s.length();i++){ // 从index开始遍历字符串
        char c = s.charAt(i); // 当前字符
        if(c == '('){ // 如果为正括号,说明出现嵌套
            // 递归得到嵌套括号内的反转字符串
            StringBuilder child = helper(s, i+1, level+1);
            // 返回值加上正括号以及嵌套括号内的反转字符串
            sb.append("(").append(child);
            // 嵌套内容已经遍历过,因此当前下标跳到嵌套子字符串之后
            i+=(child.length());
        }else if(c == ')'){ // 如果为反括号,说明嵌套结束
            // 如果为最外层,没有上层可以返回,需要继续向后循环到结束
            if(level==0){
                continue;
            }
            // 返回结果加上反括号后,反转并返回给上层递归
            return sb.append(")").reverse();
        }else{
            // 小写字母直接加到返回值中
            sb.append(c);
        }
    }
    return sb;
}

本解法运行时间为1ms。

Runtime: 1 ms, faster than 98.09% of Java online submissions for Reverse Substrings Between Each Pair of Parentheses.

Memory Usage: 34.8 MB, less than 100.00% of Java online submissions for Reverse Substrings Between Each Pair of Parentheses.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1190-reverse-substrings-between-each-pair-of-parentheses-解题思路分析/
Categories: leetcode
kwantong: