Leetcode 20.有效的括号

题目详情

原题链接点我
给定一个只包括'('，')'，'{'，'}'，'['，']'的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

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

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

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

解题思路

这里要用到栈的性质了

现在我们有一个数组

但栈的性质是先进来的先出

有两种操作 进栈和出栈

也就是 我添加了数字1,2,3 我出栈是3 刚才进来的被踢出去了 所以这个也能拿来检验有效的括号

现在我们来模拟一下

添加一个左(小)括号 进栈

轮到右小括号的时候 这个时候我们出栈

如果是右小括号对应的左小括号 则是一个合理的括号

再继续模拟一下错误情况

进来了一个左小括号和左中括号

这时候来一个右小括号)

出栈

但发现是[

所以这不是一个合理的括号

那接下来可以开始写代码了 先创建一个数组 和 字典 (查询括号对应的另一半)

a = []
i = {")":"(","}":"{","]","["}

开始遍历for循环 左括号进栈 右括号出栈 以及判断

for q in s:
    if q in ["(","[","{"]: # 左括号进栈
        a.append(q)
    else:
        if a.pop() != i[q]: # 如果出栈了不是对应的另一半
            return False
return True # 否则返回True

但题目数据范围还有1 也就意味着有 一个字符的测试示例

一个字符是构不成括号 因此要特殊判断

最终代码为

class Solution:
    def isValid(self, s: str) -> bool:
        ## 运用栈的性质

        res = [] # 先创建一个栈 栈是先进来的先出

        i = {")":"(","]":"[","}":"{"} # 对应的位置

        ## 思路
        ## 左括号进栈
        ## 当遇到右括号时出栈 如果不一致则返回false

        for q in s:
            if q in ["(","{","["]: # 如果是左括号 进栈
                res.append(q)
            else:
                if not res: # 因为题目的数据包括一个字符 防止卡特别示例 例如 s = ")"
                    return False
                if res.pop() != i[q]: # 右括号出栈 并判断
                    return False
        if res: # 也是为了防止卡特别示例 s = "["
            return False 
        return True 

但这个特殊判断我写的太麻烦 所以优化一下

class Solution:
    def isValid(self, s: str) -> bool:
        ## 运用栈的性质

        res = ["?"] # 先创建一个栈 栈是先进来的先出

        i = {")":"(","]":"[","}":"{"} # 对应的位置

        ## 思路
        ## 左括号进栈
        ## 当遇到右括号时出栈 如果不一致则返回false

        for q in s:
            if q in ["(","{","["]: # 如果是左括号 进栈
                res.append(q)
            else:
                if res.pop() != i[q]: # 右括号出栈 并判断
                    return False
        if len(res) != 1: return False
        return True 

示例代码

Python3

## 时间复杂度: O(n)
## 空间复杂度: O(n)
class Solution:
    def isValid(self, s: str) -> bool:
        ## 运用栈的性质

        res = ["?"] # 先创建一个栈 栈是先进来的先出

        i = {")":"(","]":"[","}":"{"} # 对应的位置

        ## 思路
        ## 左括号进栈
        ## 当遇到右括号时出栈 如果不一致则返回false

        for q in s:
            if q in ["(","{","["]: # 如果是左括号 进栈
                res.append(q)
            else:
                if res.pop() != i[q]: # 右括号出栈 并判断
                    return False
        if len(res) != 1: return False
        return True 

C++

// 时间复杂度: O(n)
// 空间复杂度: O(n)
// 该代码来自官方题解
class Solution {
public:
    bool isValid(string s) {
        int n = s.size();
        if (n % 2 == 1) {
            return false;
        }

        unordered_map<char, char> pairs = {
            {')', '('},
            {']', '['},
            {'}', '{'}
        };
        stack<char> stk;
        for (char ch: s) {
            if (pairs.count(ch)) {
                if (stk.empty() || stk.top() != pairs[ch]) {
                    return false;
                }
                stk.pop();
            }
            else {
                stk.push(ch);
            }
        }
        return stk.empty();
    }
};

​ PHP

class Solution {

    /**
     * @param String $s
     * @return Boolean
     */
    function isValid($s) {
        if (strlen($s)==1){return False;}
        $a = array("?");

        $b = array();
        $b[")"] = "(";
        $b["}"] = "{";
        $b["]"] = "[";
        
        for ($i = 0; $i < strlen($s); $i++){
            if ($s[$i] == "{" || $s[$i] == "(" || $s[$i] == "["){
                array_push($a,$s[$i]);
            }else{
                if(array_pop($a)!= $b[$s[$i]]){
                    return False;
                }
            }
        }
        if (count($a) == 1){
            return True;
        }else{
            return False;
        }
    }
}

感谢观看