括号题目 Leetcode

约定不等于承诺〃 2022-10-29 01:47 220阅读 0赞

# 括号系列问题 Leetcode #

## [20. 有效的括号][20.] ##

给定一个只包括 `'('`，`')'`，`'{'`，`'}'`，`'['`，`']'` 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1.  左括号必须用相同类型的右括号闭合。
2.  左括号必须以正确的顺序闭合。

**解法1:**

class Solution:
        def isValid(self, s: str) -> bool:
            while '()' in s or '[]' in s or '{}' in s:
                s = s.replace('()', '')
                s = s.replace('[]', '')
                s = s.replace('{}', '')
            if s:
                return False
            return True

**解法2：** 栈

class Solution:
        def isValid(self, s: str) -> bool:
            if len(s) % 2 != 0:
                return False
            # 此类问题使用栈： 先进后出; 队列：先进先出
            quto = { 
                ")": "(",
                "}": "{",
                "]": "["
            }
            stack = []
            for item in s:
                if item in quto: # 右括号
                    if not stack or stack[-1] != quto[item]:
                        return False
                    stack.pop()
                else: # 左括号
                    stack.append(item)
            return not stack

## [22. 括号生成][22.] ##

## [面试题 08.09. 括号][08.09.] ##

数字 `n` 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

**方法1:** 递归 + 回溯

class Solution:
        def generateParenthesis(self, n: int) -> List[str]:
            # 1. 先生成所有可能组合， 然后验证有效的；
            ans = []
            def generatep(S):
                if len(S)==2*n: # 递归结束条件
                    if valid(S):
                        ans.append(''.join(S))
                    return 
                S.append('(') # 生成 所有可能结果代码 递归 仔细学习
                generatep(S)
                S.pop()
                S.append(')')
                generatep(S)
                S.pop()
            def valid(S): # 验证括号是否有效
                temp = 0
                for c in S:
                    if c == '(':
                        temp += 1
                    else:
                        temp -= 1
                    if temp < 0:
                        return False
                return temp == 0
            generatep([])
            return ans

**方法2：** 递归 + 回溯

class Solution:
        def generateParenthesis(self, n: int) -> List[str]:
            # 回溯法 掌握的不好，对这类问题 进行归总 学习记忆
    
            ans = []
            def generatePa(S, left, right):
                if len(S) == 2*n:
                    ans.append(''.join(S))
                    return 
                if left < n:
                    S.append('(')
                    generatePa(S, left+1, right)
                    S.pop()
                if right < left:
                    S.append(')')
                    generatePa(S, left, right+1)
                    S.pop()
    
            generatePa([], 0, 0)
            return ans

## [1249. 移除无效的括号][1249.] ##

给你一个由 `'('`、`')'` 和小写字母组成的字符串 s。  
你需要从字符串中删除最少数目的 `'('` 或者 `')'` （可以删除任意位置的括号)，使得剩下的「括号字符串」有效。

请返回任意一个合法字符串。  
有效「括号字符串」应当符合以下 **任意一条** 要求：

*  空字符串或只包含小写字母的字符串
 *  可以被写作 `AB`（`A` 连接 `B`）的字符串，其中 `A` 和 `B` 都是有效「括号字符串」
 *  可以被写作 `(A)` 的字符串，其中 `A` 是一个有效的「括号字符串」

**示例 1：**

输入：s = "lee(t(c)o)de)"
    输出："lee(t(c)o)de"
    解释："lee(t(co)de)" , "lee(t(c)ode)" 也是一个可行答案。

**示例 3：**

输入：s = "))(("
    输出：""
    解释：空字符串也是有效的

**解法1：** 栈

class Solution:
        def minRemoveToMakeValid(self, s: str) -> str:
            remove_index = set()
            stack = [] 
            for i, v in enumerate(s): # 找出无效 括号索引
                if v not in "()":
                    continue
                if v == "(":
                    stack.append(i)
                elif not stack: # ) 
                    remove_index.add(i)
                else:
                    stack.pop()
            new_s = []
            # stack.extend(list(remove_index)) # 1004 ms
            remove_index = remove_index.union(set(stack)) # 104 ms
            for i, v in enumerate(s):
                if i not in remove_index:
                    new_s.append(v)
            
            return "".join(new_s)

# [678. 有效的括号字符串][678.] \* #

给定一个只包含三种字符的字符串：`（` ，`）` 和 `*`，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：

1.  任何左括号 `(` 必须有相应的右括号 `)`。
2.  任何右括号 `)` 必须有相应的左括号 `(` 。
3.  左括号 `(` 必须在对应的右括号之前 `)`。
4.  `*` 可以被视为单个右括号 `)` ，或单个左括号 `(` ，或一个空字符串。
5.  一个空字符串也被视为有效字符串。

**示例 2:**

输入: "(*)"
    输出: True

**示例 3:**

输入: "(*))"
    输出: True

**解法1:**

class Solution:
        def checkValidString(self, s: str) -> bool:
            # 定义两个栈， 双栈
            left = [] # 存储左括号
            xing = [] # 存储星号
            for index, item in enumerate(s):
                if item == "(":
                    left.append(index)
                elif item == "*":
                    xing.append(index)
                else: # 右括号, 
                    if left: # 左括号栈优先
                        left.pop()
                    elif xing:
                        xing.pop()
                    else: # 没有*，没有（， 碰到）
                        return False
            # print(left)
            # print(xing)
            # 处理 left *
            if len(left) > len(xing):
                return False
            # 处理一种情况： ( 和 * 都有剩余; 匹配(和*, 匹配完（则return True；
            count_remove = 0
            xing_index = 0
            for left_index in left:
                while xing_index < len(xing):
                    if left_index < xing[xing_index]:
                        count_remove += 1
                        xing_index += 1
                        break
                    else:
                        xing_index += 1
            return count_remove == len(left)

**解法2:** 贪心

class Solution:
        def checkValidString(self, s: str) -> bool:
            # 贪心算法
            l_min, l_max = 0, 0 # 左括号 最少，最多多少
            for item in s:
                if item == "(":
                    l_min += 1
                    l_max += 1
                elif item == ")":
                    if l_min > 0: # 最小大于0
                        l_min -= 1
                    l_max -= 1
                    if l_max < 0:
                        return False
                else:
                    if l_min > 0:
                        l_min -= 1 # 左括号 有可能减少/不变/增加
                    l_max += 1 
            return l_min == 0

## [856. 括号的分数][856.] ##

给定一个平衡括号字符串 `S`，按下述规则计算该字符串的分数：

*  `()` 得 1 分。
 *  `AB` 得 `A + B` 分，其中 `A` 和 `B` 是平衡括号字符串。
 *  `(A)` 得 `2 * A` 分，其中 `A` 是平衡括号字符串。

**示例 1：**

输入： "()"
    输出： 1

**示例 2：**

输入： "(())"
    输出： 2

**解法1：** 栈 如何计算深度？ 妙啊

+ [0, 0] (
    + [0, 0, 0] ((
    + [0, 1] (()
    + [0, 1, 0] (()(
    + [0, 1, 0, 0] (()((
    + [0, 1, 1] (()(()
    + [0, 3] (()(())
    + [6] (()(()))

class Solution:
        def scoreOfParentheses(self, S: str) -> int: 
            stack = [0] # 使用栈 记录 深度 和 得分
            for item in S:
                if item == "(": 
                    stack.append(0) # 增加深度 和 分数
                else:  # 遇到）计算当前得分
                    v = stack.pop()  # 减少深度 计算得分
                    stack[-1] += max(2*v, 1) # 有嵌套分*2，没有嵌套的为1
            return stack[-1]

## [1190. 反转每对括号间的子串][1190.] ##

给出一个字符串 `s`（仅含有小写英文字母和括号）。

请你按照从括号内到外的顺序，逐层反转每对匹配括号中的字符串，并返回最终的结果。

注意，您的结果中 **不应** 包含任何括号。

**示例 1：**

输入：s = "(abcd)"
    输出："dcba"

**示例 2：**

输入：s = "(u(love)i)"
    输出："iloveu"

**示例 4：**

输入：s = "a(bcdefghijkl(mno)p)q"
    输出："apmnolkjihgfedcbq"

提示：

*  0 <= s.length <= 2000
 *  s 中只有小写英文字母和括号
 *  我们确保所有括号都是成对出现的

**解法1:**

class Solution:
        def reverseParentheses(self, s: str) -> str:
            
            temp_list = [[]]  # 栈 
            for item in s:
                if item == "(":  
                    temp_list.append([])
                elif item == ")":
                    temp = temp_list.pop()
                    temp_list[-1].extend(temp[::-1])
                else:
                    temp_list[-1].append(item)
            # print(temp_list)
            return "".join(temp_list[-1])

## [921. 使括号有效的最少添加][921.] ##

给定一个由 `'('` 和 `')'` 括号组成的字符串 `S`，我们需要添加最少的括号（ `'('` 或是 `')'`，可以在任何位置），以使得到的括号字符串有效。

从形式上讲，只有满足下面几点之一，括号字符串才是有效的：

*  它是一个空字符串，或者
 *  它可以被写成 `AB` （`A` 与 `B` 连接）, 其中 `A` 和 `B` 都是有效字符串，或者
 *  它可以被写作 `(A)`，其中 `A` 是有效字符串。

给定一个括号字符串，返回为使结果字符串有效而必须添加的最少括号数。

**示例 4：**

输入："()))(("
    输出：4

提示：

*  S.length <= 1000
 *  S 只包含 ‘(’ 和 ‘)’ 字符。

**解法1:**

class Solution:
        def minAddToMakeValid(self, S: str) -> int:
    
            res = 0 # 添加括号数量
            left_count = 0
            for item in S:
                if item == "(":
                    left_count += 1
                else:
                    if left_count > 0:
                        left_count -= 1
                    else:
                        res += 1
            
            return res + left_count

## [1541. 平衡括号字符串的最少插入次数][1541.] ##

给你一个括号字符串 `s`，它只包含字符 `'('` 和 `')'` 。一个括号字符串被称为平衡的当它满足：

*  任何左括号 `'('` 必须对应两个连续的右括号 `'))'` 。
 *  左括号 `'('` 必须在对应的连续两个右括号 `'))'` 之前。

比方说 `"())"`， `"())(())))"` 和 `"(())())))"` 都是平衡的， `")()"`， `"()))"` 和 `"(()))"` 都是不平衡的。

你可以在任意位置插入字符 `'('` 和 `')'` 使字符串平衡。

请你返回让 `s` 平衡的最少插入次数。

**示例 1：**

输入：s = "(()))"
    输出：1
    解释：第二个左括号有与之匹配的两个右括号，但是第一个左括号只有一个右括号。我们需要在字符串结尾额外增加一个 ')' 使字符串变成平衡字符串 "(())))" 。

**解法1:**

class Solution:
        def minInsertions(self, s: str) -> int:
            # 维护左括号, 右括号两次 维护麻烦
            res = 0 # 需要插入次数
            left_count = 0  # 记录左括号个数
            s_len = len(s)
            index = 0
            while index < s_len:
                if s[index] == "(":
                    left_count += 1
                    index += 1
                else:
                    index += 1
                    if left_count > 0: # 若有左括号 则减1，否则 需要插入一个左括号
                        left_count -= 1
                    else:
                        res += 1 # 插入左括号
                    if index < s_len and s[index] == ")": # 索引+1
                        index = index + 1
                    else:
                        res += 1 # 插入右括号
            return left_count * 2 + res 
            # if left_count > 0:
                # return left_count * 2 + res
            # return res

## [1614. 括号的最大嵌套深度][1614.] ##

给你一个 `有效括号字符串` s，返回该字符串的 s 嵌套深度 。

**解法1：** 用栈

class Solution:
        def maxDepth(self, s: str) -> int:
            # 求 括号的 嵌套深度
            quto = []
            max_depth = 0
            for item in s:
                if item == "(":  # 左括号
                    quto.append(item)
                elif item == ")":
                    max_depth = max(max_depth, len(quto))
                    quto.pop()
    
            return max_depth

**解法2:**

class Solution:
        def maxDepth(self, s: str) -> int:
            # 求 括号的 嵌套深度
            left_depth = 0 # 记录l
            max_depth = 0
            for item in s:
                if item == "(":  # 左括号
                    left_depth += 1
                elif item == ")":
                    max_depth = max(max_depth, left_depth)
                    left_depth -= 1
    
            return max_depth

## [1021. 删除最外层的括号][1021.] ##

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

给出一个非空有效字符串 S，考虑将其进行原语化分解，使得：S = P\_1 + P\_2 + … + P\_k，其中 P\_i 是有效括号字符串原语。

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

**解法1:**

class Solution:
        def removeOuterParentheses(self, S: str) -> str:
            # 原语化分解
            left_count = 0
            res = ""
            primitive = ""
            for item in S:
                if item == "(":
                    if left_count != 0:
                        primitive += item
                    left_count += 1
                else:
                    left_count -= 1
                    if left_count == 0: # 得到一个原语化字符串
                        res += primitive
                        primitive = ""
                    else:
                        primitive += item
            return res

## [1111. 有效括号的嵌套深度][1111.] ##

给你一个「有效括号字符串」 `seq`，请你将其分成两个不相交的有效括号字符串，`A` 和 `B`，并使这两个字符串的深度最小。

*  不相交：每个 `seq[i]` 只能分给 `A` 和 `B` 二者中的一个，不能既属于 `A` 也属于 `B` 。
 *  `A` 或 `B` 中的元素在原字符串中可以不连续。
 *  `A.length` \+ `B.length` = `seq.length`
 *  深度最小：`max(depth(A), depth(B))` 的可能取值最小。

划分方案用一个长度为 `seq.length` 的答案数组 `answer` 表示，编码规则如下:

*  answer\[i\] = 0，seq\[i\] 分给 A 。
 *  answer\[i\] = 1，seq\[i\] 分给 B 。

如果存在多个满足要求的答案，只需返回其中任意 一个 即可。

**解法1:**

class Solution:
        def maxDepthAfterSplit(self, seq: str) -> List[int]:
            # 如何max(depth(A), depth(B)) 最小呢？ A, B 的深度尽可能接近即可 (奇偶划分)
            depth = 0
            res = []
            for item in seq:
                if item == "(":
                    depth += 1
                    res.append(depth % 2)
                else:
                    res.append(depth % 2)
                    depth -= 1
            return res

[20.]: https://leetcode-cn.com/problems/valid-parentheses/
[22.]: https://leetcode-cn.com/problems/generate-parentheses/
[08.09.]: https://leetcode-cn.com/problems/bracket-lcci/
[1249.]: https://leetcode-cn.com/problems/minimum-remove-to-make-valid-parentheses/
[678.]: https://leetcode-cn.com/problems/valid-parenthesis-string/
[856.]: https://leetcode-cn.com/problems/score-of-parentheses/
[1190.]: https://leetcode-cn.com/problems/reverse-substrings-between-each-pair-of-parentheses/
[921.]: https://leetcode-cn.com/problems/minimum-add-to-make-parentheses-valid/
[1541.]: https://leetcode-cn.com/problems/minimum-insertions-to-balance-a-parentheses-string/
[1614.]: https://leetcode-cn.com/problems/maximum-nesting-depth-of-the-parentheses/
[1021.]: https://leetcode-cn.com/problems/remove-outermost-parentheses/
[1111.]: https://leetcode-cn.com/problems/maximum-nesting-depth-of-two-valid-parentheses-strings/