167 lines
4.5 KiB
Markdown
167 lines
4.5 KiB
Markdown
# 毎日一题 - 反转每对括号间的子串
|
||
|
||
## 信息卡片
|
||
|
||
* 时间：2019-09-23
|
||
* 题目链接：https://leetcode-cn.com/problems/reverse-substrings-between-each-pair-of-parentheses
|
||
* tag：`String` `Backtracking`
|
||
## 题目描述
|
||
```
|
||
给出一个字符串 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 中只有小写英文字母和括号
|
||
我们确保所有括号都是成对出现的
|
||
```
|
||
|
||
## 参考答案
|
||
|
||
#### 思路
|
||
|
||
1. 对字符串中的字符遍历
|
||
|
||
|
||
2. 括号是有层次性的，所以这里用递归的方式处理内层的字符串，内层处理完成后回溯。返回内层有括号索引的下一个位置，以及括号内反转完成后的字符串。
|
||
|
||
|
||
3. 在2的递归过程中，原字符串也需要作为递归方法的参数传递进来
|
||
|
||
|
||
4. 递归方法的负责处理从当前位置开始到遇到对应的有括号之间的字符串，将其反转；若遇到新的左括号，创建临时的StringBuilder用于记录递归方法内反转的字符串，进入新的一层递归；递归完成后临时StringBuilder被填充并且是反转后的结果，append到上一层递归的StringBuilder中。
|
||
|
||
|
||
5. 递归回溯到最上层时，StringBuilder即为最终结果。
|
||
|
||
|
||
6. 更多代码细节可以关注下代码注释
|
||
|
||
#### 代码如下
|
||
|
||
```java
|
||
package com.jinyang.algorithms.string;
|
||
|
||
/**
|
||
* Created by Zhang.Jinyang&Hardy on 2019/10/17.
|
||
*/
|
||
public class ReverseParentheses {
|
||
|
||
public static void main(String[] args) {
|
||
|
||
/**
|
||
* 用例的类型
|
||
* (ab(cd)ef)
|
||
* ab(cd)
|
||
* ab(cd)ef
|
||
* ((ab)c)def
|
||
* abc(d(ef))
|
||
* */
|
||
String s = "ab((cd)ef)";
|
||
|
||
StringBuilder builder = new StringBuilder();
|
||
reverseParentheses(s, 0, builder, 0);
|
||
System.out.println(builder.toString());
|
||
}
|
||
|
||
/**
|
||
* leetcode 1190
|
||
* 耗时 1ms
|
||
* 内存消耗 34.6M
|
||
* */
|
||
static int reverseParentheses(String s, int index, StringBuilder stringBuilder, int leftCount) {
|
||
|
||
|
||
//遍历字符串
|
||
while (index < s.length()) {
|
||
/**
|
||
* case 当前字符为'('
|
||
* leftCount++; 记录已遍历 但未 找到相对应的右括号 的左括号数目；这里每当当前字符为'('，leftCount+1
|
||
* case: index 为 0，第一个字符为'('
|
||
* index ++, 继续遍历
|
||
* case：index 不为0， 不是第一个字符
|
||
* 递归，index++，new stringBuilder(临时存放从当前'('到其相对应的')'里的字符,不包含'('和')'), leftCount
|
||
* 递归后，new stringBuilder已被填充好 从当前'('到其相对应的')'里的字符 反转后的字符串；且返回参数为下一次要访问的字符下标index
|
||
* leftCount --；因为进入递归后返回时已经将 当前'(' 与其响应的 ')' 内的字符反转，所以左括号数减1
|
||
* 递归前的 stringBuilder append 递归后，已反转的 new stringBuilder
|
||
* 继续遍历.
|
||
* */
|
||
if (s.charAt(index) == '(') {
|
||
leftCount++;
|
||
if (index != 0) {
|
||
StringBuilder sTemp = new StringBuilder();
|
||
index = reverseParentheses(s, index + 1, sTemp, leftCount);
|
||
leftCount--;
|
||
stringBuilder.append(sTemp);
|
||
continue;
|
||
}
|
||
|
||
index++;
|
||
continue;
|
||
}
|
||
|
||
/**
|
||
* case 当前字符为')'
|
||
* 反转stringBuilder里的字符位置；
|
||
* index++；
|
||
* case：当前leftCount >1 那么当前是在递归过程中
|
||
* return index;//回溯
|
||
* case: 当前leftCount <=1 当前不是递归
|
||
* 继续遍历;
|
||
* */
|
||
if (s.charAt(index) == ')') {
|
||
stringBuilder.reverse();
|
||
index++;
|
||
if (leftCount > 1) {
|
||
return index;
|
||
} else {
|
||
continue;
|
||
}
|
||
}
|
||
|
||
/**当前字符不是'(' 或 ')'
|
||
* 当前stringBuilder append 当前下标对应的字符
|
||
* index++
|
||
* 继续遍历
|
||
* */
|
||
stringBuilder.append(s.charAt(index));
|
||
index++;
|
||
}
|
||
return index;
|
||
}
|
||
|
||
|
||
}
|
||
|
||
|
||
```
|
||
|
||
|
||
## 优秀解答
|
||
|
||
>暂缺
|