[数据结构与算法]字符串-有效的括号-简中-20210912

字符串-LC20有效的括号-简单-20210912

1. 题目描述

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

有效字符串需满足：

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

示例：

输入：s = "()"
输出：true

输入：s = "()[]{}"
输出：true

输入：s = "(]"
输出：false

输入：s = "([)]"
输出：false

输入：s = "{[]}"
输出：true

提示：

• 1 <= s.length <= 10^4
• s 仅由括号 '()[]{}' 组成

2. 题目解答

栈思想
先出现的左括号后匹配，后出现的左括号要先匹配

• 左括号依次入栈
• 当遇到一个右括号时，需要将一个相同类型的左括号闭合。此时，我们可以取出栈顶的左括号并判断它们是否是相同类型的括号
  • 如果不是相同的类型，或者栈中并没有左括号，那么字符串s无效，返回False。
• 在遍历结束后，如果栈中没有左括号，说明我们将字符串 s 中的所有括号闭合，返回True，否则返回False。

注意到有效字符串的长度一定为偶数，因此如果字符串的长度为奇数，我们可以直接返回False，省去后续的遍历判断过程。

以下方法复杂度：

时间复杂度：$O(n)$，n 是字符串 s 的长度
空间复杂度：$O(n+|\Sigma |)$，其中 $\Sigma$ 表示字符集，本题中字符串只包含 6 种括号，$|\Sigma |=6$，栈中的字符数量为 $O(n)$，而哈希表使用的空间为 $O(|\Sigma |)$，相加即可得到总空间复杂度。

2.1 尝试-最后ac

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        dic = {'(': ')', '[': ']', '{': '}'}
        for i in s:
            if i in dic.keys():
                stack.append(i)
            else:
                if not stack: return False  # 第一个是反括号
                tem = stack.pop()
                if dic[tem] != i:
                    return False
        if stack :
            return False
        else:
            return True

尝试过程中未考虑到的用例：
"){"  # stack此时为空，要加判断
"]"

"((" # 遍历结束后，stack不为空
"["

2.2 官方题解+自己答案优化

1. 注意到有效字符串的长度一定为偶数，因此如果字符串的长度为奇数，我们可以直接返回False，省去后续的遍历判断过程。
2. stack为空返回True，直接用 not stack代替

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) % 2 == 1: return False  # 减少奇数的判断过程
        stack = []
        dic = {'(': ')', '[': ']', '{': '}'}
        for ch in s:
            if ch in dic:  # 简化写法
                stack.append(ch)
            else:
                if not stack: return False  # 第一个是反括号，可以和下一个条件合并，如下
                if dic[stack.pop()] != ch:
                    return False
        return not stack  # 简化写法

    
class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) % 2 == 1: return False  # 减少奇数的判断过程
        stack = []
        dic = {'(': ')', '[': ']', '{': '}'}
        for ch in s:
            if ch in dic:  # 简化写法
                stack.append(ch)
            else:
                if not stack or dic[stack.pop()] != ch: return False  # 将两个条件合并
        return not stack  # 简化写法

2.3 评论区优解

• 栈 stack 为空： 此时 stack.pop() 操作会报错；因此，我们采用一个取巧方法，给 stack 赋初值 ? ，并在哈希表 dic 中建立key: '?'，value:'?' 的对应关系予以配合。此时当 stack 为空且 c 为右括号时，可以正常提前返回 false；
• 字符串 s 以左括号结尾： 此情况下可以正常遍历完整个 s，但 stack 中遗留未出栈的左括号；因此，最后需返回 len(stack) == 1，=1时只剩下?，以判断是否是有效的括号组合。

class Solution:
    def isValid(self, s: str) -> bool:
        dic = {'{': '}',  '[': ']', '(': ')', '?': '?'}
        stack = ['?']
        for c in s:
            if c in dic: stack.append(c)
            elif dic[stack.pop()] != c: return False 
        return len(stack) == 1
                
class Solution:
    def isValid(self, s: str) -> bool:
        stack = ['?']
        dic = {'(': ')', '[': ']', '{': '}', '?': '?'}
        for ch in s:
            if ch in dic:
                stack.append(ch)
            else:  
                if dic[stack.pop()] != ch:  #可以如上用elif
                    return False
        return len(stack) == 1

3. 测试用例

1. 空字符串
2. 奇数个字符串
3. )]右括号先出现
4.((最后剩余左括号未匹配

字符串-LC678有效的括号-中等-20210912

1. 题目描述

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

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

示例：

输入: "()"
输出: True

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

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

注意：

1. 字符串大小将在 $[1，100] $范围内。

2. 题目解答

2.1 尝试-未完全通过

思路：

• 在=
• C
• 需要

时间复杂度：$O(n)$
空间复杂度：$O(n)$

class Solution:
    def checkValidString(self, s: str) -> bool:
        stack = []
        stack_r = []
        stack_ = []
        for i in s:
            if i == '(':
                stack.append(i)
            elif i == ')' and stack:
                stack.pop()
            elif i == ')' and not stack:
                stack_r.append(i)
            else:
                stack_.append(i)
        if len(stack_) >= (len(stack) + len(stack_r)):
            return True
        else:
            return False

未通过用例：

* ( 和 )*的情况，星号充当不了另一个括号

"(((((*(()((((*((**(((()()*)()()()*((((**)())*)*)))))))(())(()))())((*()()(((()((()*(())*(()**)()(())""((((()(()()()*()(((((*)()*(**(())))))(())()())(((())())())))))))(((((())*)))()))(()((*()*(*)))(*)()"

2.2 模拟

• 思路：遍历两次，第一次顺序，第二次逆序。

  • 第一次遇到左括号加一，右括号减一，星号加一，最后保证cnt >= 0,也就是可以保证产生的左括号足够
  • 第二次遇到右括号加一，左括号减一，星号加一，最后保证cnt >= 0,也就是可以保证产生的右括号足够

• 当两次遍历都是True，那么说明有效

  时间复杂度：$O(n)$
  空间复杂度：$O(1)$

class Solution:    def checkValidString(self, s: str) -> bool:        def help(a):            cnt = 0            for c in s if a == 1 else reversed(s):                if c == '(': cnt += a                 if c == ')': cnt += -a                if c == '*': cnt += 1                if cnt < 0:                    return False            return True        return help(1) and help(-1)

2.3 动规

问题？python怎么获得入栈时的顺序

思路：

• 左括号入栈left，星号入栈star
• 右括号先匹配left出栈，若left为空匹配star，都为空，返回False
• 若最后left为空为True，不为空
  • 如果star为空，返回False
  • 如果star不为空，判断star出现是否是在left里左括号的右侧？？

2.4 栈

问题？python怎么获得入栈时的顺序

思路：

• 左括号入栈left，星号入栈star
• 右括号先匹配left出栈，若left为空匹配star，都为空，返回False
• 若最后left为空为True，不为空
  • 如果star为空，返回False
  • 如果star不为空，判断star出现是否是在left里左括号的右侧？？

3. 测试用例

1. 空字符串；只有一个空格字符；连续多个空格2. 输入的字符串中包含空格（位置：最前面/最后面/中间；连续多个空格）3. 输入的字符串中不包含空格

4. 相关题目/拓展

22. 括号生成

32. 最长有效括号

301. 删除无效的括号