题1021：类型：栈
- 题目：
有效括号字符串为空 ("")、"(" + A + ")" 或 A + B，其中 A 和 B 都是有效的括号字符串，+ 代表字符串的连接。例如，""，"()"，"(())()" 和 "(()(()))" 都是有效的括号字符串。
如果有效字符串 S 非空，且不存在将其拆分为 S = A+B 的方法，我们称其为原语，其中 A 和 B 都是非空有效括号字符串。
给出一个非空有效字符串 S，考虑将其进行原语化分解，使得：S = P_1 + P_2 + ... + P_k，其中 P_i 是有效括号字符串原语。对 S 进行原语化分解，删除分解中每个原语字符串的最外层括号，返回 S 。
示例 ：
输入："(()())(())"
输出："()()()"
解释：
输入字符串为 "(()())(())"，原语化分解得到 "(()())" + "(())"，
删除每个部分中的最外层括号后得到 "()()" + "()" = "()()()"。
提示：
S.length <= 10000
S[i] 为 "(" 或 ")"
S 是一个有效括号字符串
-
方法一、直接用栈实现
1、新建栈，临时存储字符并且代替计数器；
2、遍历字符串：左括号入栈，右括号出栈；
3、若栈为空，找到了一个完整的原语，截取并拼接。
class Solution {
public String removeOuterParentheses(String S) {
//新建栈,临时存储字符，代替计数器
Stack<Character> s = new Stack<>();
StringBuilder sb = new StringBuilder();//结果字符串
int sign = 0; // 原语左标识，i是右标识
//遍历字符串，满足原语条件,直接定位剔除最外层括号后的字符串
for(int i = 0;i < S.length(); ++i){
char ch = S.charAt(i);
if(ch == '('){
s.push(ch);
}else if(ch == ')') { // 此处判断条件可删除
s.pop();
}
// 判断栈是否为空，若为空，找到了一个完整的原语
if(s.isEmpty()){
// 删除原语子串最外层()，并拼接其余子串
sb.append(S.substring(sign+1 , i)); // [ ),左开右闭
sign = i + 1; // 初始化原语左标识初始位置
}
}
return sb.toString();
}
}
-
方法二、用数组代替栈
1、直接用数组取代栈，但是逻辑上还是栈；
2、将原字符串转换为字符数组进行遍历，节省了循环中多次调用charAt()方法的时间；
3、读取到左括号: 若该左括号之前有数据，当前为原语 ; 同理，读取到右括号，匹配后数组内仍不为0，当前为原语，最后拼接。
注意：第三步的思想中，判断出的原语已经包含了剔除最外层括号的步骤。
class Solution {
public String removeOuterParentheses(String S) {
//用数组代替栈，逻辑上还是栈
int len = S.length();
int index = -1; // '栈'顶索引
char[] stack = new char[len];
//结果字符串
StringBuilder sb = new StringBuilder();
// 原字符串转化为字符数组
char[] s = S.toCharArray();
// 遍历字符数组
for(int i = 0;i < len; ++i){
char ch = s[i];
if(ch == '('){
// 判断在前
if(index > -1){
sb.append(ch); // 拼接子串
}
stack[++index] = ch;
}else if(ch == ')') {
stack[index--] = '\u0000';
// 判断在右括号匹配后
if(index > -1){
sb.append(ch);
}
}
}
return sb.toString();
}
}
-
方法三、计数器代替栈
1、直接用计数器代替，左括号+1，右括号-1，依然采用栈的逻辑进行判断；
2、将原字符串转换为字符数组进行遍历，节省了循环中多次调用charAt()方法的时间；
3、读取到左括号: 若该左括号之前有数据（计数器大于0），当前为原语 ，然后计数器加1; 同理，读取到右括号，匹配后数组内仍不为0（计数器减1后仍大于0），当前为原语，最后拼接。
注意：第三步的思想中，判断出的原语已经包含了剔除最外层括号的步骤。
class Solution {
public String removeOuterParentheses(String S) {
//用数组代替栈，逻辑上还是栈
int len = S.length();
// 计数器，左括号+1，右括号-1
int count = 0;
//结果字符串
StringBuilder sb = new StringBuilder();
// 原字符串转化为字符数组
char[] s = S.toCharArray();
for(int i = 0;i < len; ++i){
char ch = s[i];
if(ch == '('){
// 根据计数判断左右括号是否为原语
if(count > 0){ // 此前有数据
sb.append(ch);
}
count++;
}else if(ch == ')') {
count--;
if(count > 0){ // 右括号之后不为0，自减后仍有数据
sb.append(ch);
}
}
}
return sb.toString();
}
}
