删除最外层的括号

说在前面

🎈 算法并不一定都是很难的题目，也有很多只是一些代码技巧，多进行一些算法题目的练习，可以帮助我们开阔解题思路，提升我们的逻辑思维能力，也可以将一些算法思维结合到业务代码的编写思考中。简而言之，平时进行的算法习题练习带给我们的好处一定是不少的，所以让我们一起来养成算法练习的习惯。今天练习的题目是一道比较简单的题目 ->删除最外层的括号

问题描述

有效括号字符串为空 ""、"(" + 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 是一个有效括号字符串

思路分析

首先我们应该先理解一下题目意思，题目会给我们一个字符串，字符串仅由 ( 和 ) 组成，我们需要删除每个原语字符串的最外层括号，所以我们需要先理解一下什么是原语字符串,题目中说道：如果有效字符串 s 非空，且不存在将其拆分为 s = A + B 的方法，我们称其为原语（primitive） ，其中 A 和 B 都是非空有效括号字符串。也就是说原语是由多个有效括号字符串拼接而成，所以我们需要进一步理解什么是有效括号字符串，这里的有效括号字符串表示一个完整闭合的括号字符串，例如：""，"()"，"(())()" 和 "(()(()))" 都是有效的括号字符串。

理解了题目说到的各个名词的意思之后，我们便可以开始进行解题了，我们需要先将字符串原语化，也即是找出字符串中所有的有效括号字符串，再将每个有效括号字符串的最外层删除后再拼接起来即可。

因为题目中说到: s 是一个有效括号字符串，所以我们只需要遍历字符串，统计当前遍历过的左括号和右括号的数量，当左括号数量与右括号数量相等时，则说明当前部分为一个有效的括号字符串，去掉其最外层的括号，拼接到结果字符串即可。

AC 代码

完整代码如下：

/**
 * @param {string} s
 * @return {string}
 */
var removeOuterParentheses = function (s) {
  let res = "",
    cnt = 0;
  let tmp = "";
  for (let i = 0; i < s.length; i++) {
    if(s[i] === ')') cnt--;
    if (cnt == 0) {
      res += tmp;
      tmp = "";
    }
    if (cnt > 0) tmp += s[i];
    if(s[i] === '(') cnt++;
  }
  return res;
};

公众号

关注公众号『前端也能这么有趣』，获取更多新鲜内容。

说在后面

🎉 这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打羽毛球 🏸 ，平时也喜欢写些东西，既为自己记录 📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解 🙇，写错的地方望指出，定会认真改进 😊，偶尔也会在自己的公众号『前端也能这么有趣』发一些比较有趣的文章，有兴趣的也可以关注下。在此谢谢大家的支持，我们下文再见 🙌。