题目描述
给出一个非空有效字符串S，考虑将其进行原语化分解。
使得：S=P_1+P_2+...+P_k，其中P_i是有效括号字符串原语。
对S进行原语化分解，删除分解中每个原语字符串的最外层括号，返回S。
➢ 有效括号字符串：例如："( )"，"( ( ) ) ( )" 和 "( ( ) ( ( ) ) )"
➢ 原语：如果有效字符串S非空，且不能将其拆分为 S=A+B，我们称其为原语（primitive），其中A和B都是非空有效括号字符串。
数据结构
- 字符串、数组、栈
算法思维
- 遍历、计数器、累加、栈操作
解题要点
- 使用两个变量作为计数器，分别记录 "(" 和 ")" 的个数，左右括号数量相等时则说明发现了一个原语
- 字符串截取时，区间的 左闭右开 性质
- 栈的相关概念
栈（stack）
限定仅在表尾进行插入和删除操作的线性表
栈顶（Top）：操作数据的一端，即表尾
栈底（Bottom）：线性表的另一端，即表头
特点：LIFO（Last In First Out），后进先出
基本操作：
➢ 进栈：push()，在栈顶插入元素，入栈、压栈
➢ 出栈：pop()，从栈顶删除数据
➢ 查栈：peek()，查看栈顶数据，不取出
➢ 判断空：isEmpty()
解题步骤
一. Comprehend 理解题意
题目基本信息
- 有效括号字符串：括号必然成对出现
- 给定字符串 S 非空，但返回结果可能为空
- 原语化分解只需要进行一级
- 返回的是各个原语删除了最外层括号后拼接成的新字符串
附加信息
- S.length <= 10000
- S[i] 为 "(" 或 ")"
解题思路
- 解法一：分解、删除、合并
- 解法二：定位、直取、合并
二. Choose 选择数据结构与算法
解法一：分解、删除再合并
- 先分解成字符串原语
- 再删除每部分最外层括号
- 返回各部分合并后的结果
数据结构：字符串、数组
算法思维：遍历、计数器、累加
简化过程：既然最外层的括号是要删除的，直接取最外层括号内部的字符串是否更简单呢？
解法二：定位、直取再合并
- 对原字符串进行原语识别
- 获取不包含最外层括号的子串
- 将各部分拼接返回
数据结构：字符串、数组
算法思维：遍历、计数器、累加
三. Code 编码实现基本解法
解法一：分解、删除再合并
- 定义容器存储原语子串：
new ArrayList<String>(); - 定义左括号、右括号计数器：
int left = 0, right = 0; - 遍历字符串，读取到括号时对应计数器自增
- 检查是否到达原语结尾，截取原语子串并添加到容器中
- 遍历容器，删除最外层括号后合并成新串
边界问题
- 遍历字符串，注意索引越界：i < S.length()
- 截取原语字符串时，注意起止索引：[start, end)
细节问题
- 需要记录上一次截取原语子串之后的位置
- 删除原语子串的最外层括号，其实就是重新截取
class Solution {
public String removeOuterParentheses(String S) {
int len = S.length();
// 1.定义容器存储原语子串
List < String > list = new ArrayList < > ();
// 2.定义左括号、右括号计数器
int left = 0, right = 0, lastOpr = 0;
// 3.遍历字符串，读取到括号时对应计数器自增
for(int i = 0; i < len; i++) {
char c = S.charAt(i);
if(c == '(') {
left++;
}
else if(c == ')') {
right++;
}
// 4.检查是否到达某个原语结尾，截取原语子串添加到容器
if(left == right) {
list.add(S.substring(lastOpr, i + 1));
lastOpr = i + 1;
}
}
// 5.遍历容器中的原语子串，删除最外层后合并成新串
StringBuilder sb = new StringBuilder();
for(String s: list) {
sb.append(s.substring(1, s.length() - 1));
}
return sb.toString();
}
}
时间复杂度：O(n) -- 字符串的遍历 O(n)，各个原语的遍历 O(n)
空间复杂度：O(n) -- 原语子串 O(n)，存放原语子串的容器 O(n)，生成的新字符串 O(n)，计数器 O(1)
执行耗时：6 ms，击败了 49.10% 的Java用户
内存消耗：38.6 MB，击败了 39.07% 的Java用户
解法二：定位、直取再合并
- 定义容器存储删除外层括号后的原语子串：
new StringBuilder(); - 定义左括号、右括号计数器：
int left = 0, right = 0; - 遍历字符串，读取到括号时对应计数器自增
- 检查是否到达原语结尾，截取不包含最外层的原语子串并拼接到容器中
class Solution {
public String removeOuterParentheses(String S) {
int len = S.length();
// 1.定义容器存储删除外层括号后的原语子串
StringBuilder sb = new StringBuilder();
// 2.定义左括号、右括号计数器
int left = 0, right = 0, lastOpr = 0;
// 3.遍历字符串，读取到括号时对应计数器自增
for(int i = 0; i < len; i++) {
char c = S.charAt(i);
if(c == '(') {
left++;
}
else if(c == ')') {
right++;
}
// 4.检查是否到达某个原语结尾，截取不包含最外层的原语子串添加到容器
if(left == right) {
sb.append(S.substring(++lastOpr, i));
lastOpr = i + 1;
}
}
return sb.toString();
}
}
时间复杂度：O(n) -- 字符串的遍历 O(n)，各个原语的遍历 O(n)
空间复杂度：O(n) -- 原语子串 O(n)，存放原语子串的容器 O(n)，生成的新字符串 O(n)，计数器 O(1)
执行耗时：4 ms，击败了 62.60% 的Java用户
内存消耗：38.5 MB，击败了 51.77% 的Java用户
四. Consider 思考更优解
剔除无效代码，优化空间消耗
- 只需要一个计数器："(" 自增 ； ")" 自减
- 如果字符串数据只是两两配对怎么处理？每个原语的开始和结束标识都不同，此时用计数器无法满足需求
- 因此考虑：有没有一种支持后进先出的数据结构？
最优解：栈解法
数据结构：字符串、栈
算法思维：遍历、栈操作、累加
五. Code 编码实现最优解
最优解：栈解法
- 使用数组模拟一个栈，临时存储字符，替代计数器：
push(Character) ; pop(); isEmpty() - 遍历字符串，根据情况进行入栈/出栈操作
读取到左括号，左括号入栈；读取到右括号，左括号出栈 - 判断栈是否为空，若为空，找到了一个完整的原语
- 截取不含最外层括号的原语子串并进行拼接
边界问题
- 遍历字符串，注意索引越界：i < S.length()
- 截取原语字符串时，注意起止索引：[start, end)
细节问题
- 需要记录上一次截取原语子串之后的位置
- 右括号无需进栈
class Solution {
public String removeOuterParentheses(String S) {
Stack < Character > stack = new Stack < > ();
StringBuilder sb = new StringBuilder();
int lastOpr = 0;
//1.遍历字符串
for(int i = 0; i < S.length(); i++) {
char c = S.charAt(i);
//2.如果是左括号，入栈
if(c == '(') {
stack.push(c);
}
else if(c == ')') {
//3.如果是右括号，出栈
stack.pop();
}
//4.如果栈空了，则说明读取了一个原语
if(stack.isEmpty()) {
sb.append(S.substring(++lastOpr, i));
lastOpr = i + 1;
}
}
return sb.toString();
}
//自定义栈
class Stack < E > {
Object[] arr = new Object[10000];
int index = -1;
int size = 0;
public void push(E e) {
arr[++index] = e;
size++;
}
public E pop() {
E e = peek();
//需要进行非空判断
if(e != null) {
arr[index--] = null;
size--;
}
return e;
}
public E peek() {
//需要进行非空判断
return index < 0 ? null : (E) arr[index];
}
public boolean isEmpty() {
return size == 0;
}
}
}
时间复杂度：O(n) -- 字符串的遍历 O(n)，各个原语的遍历 O(n)
空间复杂度：O(n) -- 原语子串 O(n)，生成的新字符串 O(n)，使用栈临时存储数据 O(n/2)，存放原语子串的容器 O(n)，计数器 O(1)
执行耗时：9 ms，击败了 29.76% 的Java用户
内存消耗：38.1 MB，击败了 97.68% 的Java用户
栈解法的优化 #1
- 直接用数组取代栈
创建数组、栈顶索引，使用数组操作入栈和出栈 - 将原字符串转为数组进行遍历：
char[] s = S.toCharArray(); - 去掉截取子串的操作，将原语字符直接拼接
读取到左括号：栈中有数据，则当前字符必属原语
读取到右括号：匹配后栈大小不为 0，则当前字符必属原语
class Solution {
public String removeOuterParentheses(String S) {
StringBuilder result = new StringBuilder();
// 1.直接用数组取代栈
int index = -1; // 栈顶索引
int len = S.length();
char[] stack = new char[len];
char[] s = S.toCharArray();
// 2.遍历字符串，根据情况进行入栈 / 出栈操作
for(int i = 0; i < len; i++) {
char ch = s[i];
if(ch == '(') { // 遇到左括号，左括号入栈
// 3.去掉截取子串的操作，将原语字符直接拼接
if(index > -1) { // 此前有数据，当前必属原语
result.append(ch);
}
stack[++index] = ch;
}
else /*if (ch == ')')*/ { // 遇到右括号，左括号出栈
stack[index--] = '\u0000'; // 栈顶的左括号出栈
if(index > -1) {
result.append(ch);
}
}
}
return result.toString();
}
}
时间复杂度：O(n) -- 遍历整个字符串 O(n)
空间复杂度：O(n) -- 代替栈的数组 O(n)，字符数组 O(n)，生成的新字符串 O(n)
执行耗时：3 ms，击败了 90.24% 的Java用户
内存消耗：38.3 MB，击败了 97.90% 的Java用户
栈解法的优化 #2
- 用 计数器(int) 取代字符数组，实现栈的功能
使用计数器的 自增和自减 模拟 入栈和出栈
注意：之所以可以这样做是因为原语的起始和符号始终不变，始终为 "(" 和 ")"
class Solution {
public String removeOuterParentheses(String S) {
//0.用计数器替换栈
int size = 0; //栈大小计数器
char[] charArr = S.toCharArray();
StringBuilder sb = new StringBuilder();
//1.遍历字符串 -> 遍历字符数组
for(int i = 0; i < charArr.length; i++) {
char c = charArr[i];
//2.如果是左括号，且栈中有数据，则当前字符属于原语
if(c == '(' && size++ != 0) sb.append(c);
//3.如果是右括号，且配对后栈大小不为0，则当前字符属于原语
else if(c == ')' && --size != 0) sb.append(c);
}
return sb.toString();
}
}
时间复杂度：O(n) -- 遍历整个字符串 O(n)
空间复杂度：O(n) -- 代替栈的数组 O(n)，计数器 O(1)，字符数组 O(n)，生成的新字符串 O(n)
执行耗时：2 ms，击败了 100.00% 的Java用户
内存消耗：38.2 MB，击败了 93.63% 的Java用户
六. Change 变形与延伸
题目变形
- （练习）删除最内层的括号
- （练习）用链表实现一个栈（链栈）
延伸扩展
- （练习）逆波兰表达式求值：给定数字和运算符，根据规则计算出结果
- 子程序调用：方法依次进栈，最后调用的最先结束
