第1.3篇·删除最外层的括号

算法是求职的敲门砖，大厂面试一面几乎都会问算法题，以此来考察候选人的思维逻辑及编码能力。

今天要AC的题目叫做「删除最外层的括号」，在 leetcode 上的原题链接为：https://leetcode-cn.com/problems/remove-outermost-parentheses/。

1. 题目

有效括号字符串为空 “”、”(“ + A + “)” 或 A + B ，其中 A 和 B 都是有效的括号字符串，+ 代表字符串的连接。

例如，””，”()”，”(())()” 和 “(()(()))” 都是有效的括号字符串。
如果有效字符串 s 非空，且不存在将其拆分为 s = A + B 的方法，我们称其为原语（primitive），其中 A 和 B 都是非空有效括号字符串。

给出一个非空有效字符串 s，考虑将其进行原语化分解，使得：s = P_1 + P_2 + … + P_k，其中 P_i 是有效括号字符串原语。

对 s 进行原语化分解，删除分解中每个原语字符串的最外层括号，返回 s 。

示例 1： 输入：s = "(()())(())" 输出："()()()" 解释： 输入字符串为 "(()())(())"，原语化分解得到 "(()())" + "(())"， 删除每个部分中的最外层括号后得到 "()()" + "()" = "()()()"。 示例 2： 输入：s = "(()())(())(()(()))" 输出："()()()()(())" 解释： 输入字符串为 "(()())(())(()(()))"，原语化分解得到 "(()())" + "(())" + "(()(()))"， 删除每个部分中的最外层括号后得到 "()()" + "()" + "()(())" = "()()()()(())"。 示例 3： 输入：s = "()()" 输出："" 解释： 输入字符串为 "()()"，原语化分解得到 "()" + "()"， 删除每个部分中的最外层括号后得到 "" + "" = ""。

提示：

• 1 <= s.length <= 105
• s[i] 为 '(' 或 ')'
• s 是一个有效括号字符串

2. 解题思路

这道题目题意还挺绕的，几个示例输入输出分辨度也不看，初时看得我眼花缭绕，不知所云，示例中的“解释”部分更是扰乱视线的绝好帮手。要是认真从“解释”部分入手来寻找解题思路，那将进入一条复杂的求解之路。

得益于高人指点，我找到了一条非常简单的数学解法——找规律！

本题最大的难点就是需要知道哪个左括号和右括号是有效的，既然一时找不到，那就拿示例来找规律，这时候我们需要借助计数器来做标记，当遇到左括号时计数器加1，当遇到右括号时计数器减1。

示例1:
遍历前值0121210121，遍历前计时器数值为1、2、1、2、1、2
输入字符(()())(())，遍历有效括号字符为左 右 左 右 左 右
遍历后值1212101210，遍历后计时器数值为2、1、2、1、2、1
示例2
遍历前值012121012101212321，遍历前计时器数值为1、2、1、2、1、2、1、2、1、2、3、2
输入字符(()())(())(()(()))，遍历有效括号字符为左 右 左 右 左 右 左 右 左 左 右 右
遍历后值121210121012123210，遍历后计时器数值为2、1、2、1、2、1、2、1、2、3、2、1
示例3，都不是有效括号
遍历前值0101
输入字符()()
计数器值1010

从上述计数器的结果来看：

• 有效左括号：遍历前计数器值大于0
• 有效右括号：遍历前计数器值大于1

但是如果找不到这个规律，那只能按照“解释” 部分的逻辑来进行字符串的判定，用栈来解决再好不过。

用 Java 实现上述的思路就是：

上述示例代码在 leetcode 上的执行结果是：

最后，本文收录于个人语雀知识库: 我所理解的后端技术，欢迎来访。