題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圣勒、將原字符串轉換為字符數組進行遍歷，節(jié)省了循環(huán)中多次調用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、將原字符串轉換為字符數組進行遍歷壹蔓，節(jié)省了循環(huán)中多次調用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();
}
}
