当前位置：首页 > 算法 > 正文内容

删除最外层括号

CarlZhou2年前 (2022-03-25)算法2050

# 删除最外层括号
简单/计数器、累加、栈

### 学习目标
- 了解算法题的解题思路
- 栈的特点
- 栈的应用

### 题目描述
给出一个**非空**有效字符串S,考虑将其进行**原语化分解**
使得：s=P_1+P_2+...+P_K,其中P_i是有效括号字符串原语
对s进行原语化**分解，删除**分解中每个原语字符串的**最外层括号，返回s**

> 有效括号字符串：例如："()","(())()"和"(()(()))"
> 原语：如果有效字符串s非空，且不能将其拆分为s=A+B,我们将其称为**原语（primitive）**,其中A和B都是**非空有效括号字符串**

![](http://szv5.cn/zb_users/upload/2022/03/202203252221575043552.png)

#### 一、Comprehend理解题意
**题目基本信息**
- **有效括号字符串**：括号必然成对出现
- 给定字符串s非空，但返回结果可能为空
- 原语化分解只需要进行一级
- 返回删除每个原语的**最外层**括号后的字符串
**附加信息**
- s.length <= 10000
- s[i]为"("或")"

**解法一：暴力解法**
- 先分解成字符串原语
- 再删除每部分最外层括号
- 返回各部分合并后的结果

**解法二：优化解法**
- 对原字符串进行原语识别
- 获取不包含最外层括号的子串
- 将各部分拼接返回

#### 二、Choose数据结构及算法思维选择

**解法一：分解、删除再合并**
- 数据结构：字符串、数组
- 算法思维：遍历、计数器、累加

**解法二：定位、直取再合并**
- 数据结构：字符串、数组
- 算法思维：遍历、计数器、累加

#### 三、Code基本解法及编码实现
解法一：暴力解法思路分析
1、定义容器存储原语子串
   new ArrayList<String>();
2、定义左括号、右括号计数器
   int left = 0,right = 0;
3、遍历字符串，读取到括号时对应计数器自增
4、检查是否到达原语结尾，截取原语子串并添加到容器中

**边界和细节问题**
1、边界问题：
   遍历字符串，注意索引越界：i < s.length()
   截取原语字符串时，注意起止索引：[start,end]
2、细节问题
   需要记录上一次截取原语子串之后的位置
   删除原语子串的最外层括号，其实就是重新截取

![](http://szv5.cn/zb_users/upload/2022/03/202203252246449885571.png)

解法二：优化解法思路分析
1、定义容器存储删除外层括号后的原语子串
   new StringBuilder();
2、定义左括号、右括号计数器：
   int left=0,right=0;
3、遍历字符串，读取到括号时对就计数器自增
4、检查是否到达原语结尾，截取**不包含最外层的**原语子串并拼接到容器中
![](http://szv5.cn/zb_users/upload/2022/03/202203252256474136728.png)

#### 四、Consider 思考更优解
1. **剔除无效代码或优化空间消耗**
 - 只需要一个计数器："("自增，")"自减
 - 如果字符串数据只是两两配对怎么处理？
 - 有没有一种支持**后进先出**的数据结构
2. **寻找更好的算法思维**
 - 借鉴其它算法
 
#### 五、Code 最优解思路及编码实现
**关键知识点：栈（Stack）**
- 限定仅在**表尾**进行插入和删除操作的线性表
- 栈顶(Top):操作数据的一端，即表尾
- 栈底(Bottom):线性表的另一端，即表头
- 特点LIFO,后进先出
- 基本操作:
  - 进栈:push(),在栈顶插入元素，入栈、压栈
  - 出栈:pop(),从栈顶删除数据
  - 判断空：isEmpty()
![](http://szv5.cn/zb_users/upload/2022/03/202203252304203692311.png)

**最优解：栈解法**
1、使用数组模拟一个栈，临时存储字符，替代计数器
2、遍历字符串，根据情况进行入栈/出栈操作
   读取到左括号，左括号入栈
   读取到右括号，左括号出栈
3、判断栈是否为空，若为空，找到了一个完整的原语
4、截取不含最外层括号的原语子串并进行拼接

**边界和细节问题**
1、边界问题
   遍历字符串，注意索引越界：i < s.length()
   截取原语字符串时，注意起止索引:[start,end]
2、细节问题
   需要记录上一次截取原语子串之后的位置
   右括号无须进栈
   
![](http://szv5.cn/zb_users/upload/2022/03/202203252310281061268.png)

**最优解：优化代码，直接用数组取代栈**
1、直接用数组取代栈
   创建数组、栈顶索引，使用数组操作入栈和出栈
2、将原字符串转为数组进行遍历
   char[] chars = s.toCharArray();
3、去掉截取子串的操作，将原语字符串直接拼接
   读取到左括号:此前有数据，当前必属原语
   读取到右括号:匹配后不为0，当前必属原语
![](http://szv5.cn/zb_users/upload/2022/03/202203252316082232148.png)

![](http://szv5.cn/zb_users/upload/2022/03/202203252316388937351.png)

#### 六、Change变形延伸
**题目变形**
- 删除最内层的括号
- 用链表实现一个栈（链栈）
**延伸扩展**
- 逆波兰表达式求值：给定数字和运算符，根据规则计算出结果
- 子程序调用：方法依次进栈，最后调用的最先结束
本题来源
Leetcode[1021] https://leetcode-cn.com/problems/remove-outermost-parentheses/

#### 测试结果
![](http://szv5.cn/zb_users/upload/2022/03/202203252324152930922.png)
代码：https://gitee.com/carl001/leetcode_in_action