[0020] 有效的括号

• GitHub
• http://leetcode.xuezhisd.top/post/f7e14fbb.html
• https://leetcode.com/problems/valid-parentheses
• https://leetcode-cn.com/problems/valid-parentheses

题目描述

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

有效字符串需满足：

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

注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true

示例 2:

输入: "()[]{}"
输出: true

示例 3:

输入: "(]"
输出: false

示例 4:

输入: "([)]"
输出: false

示例 5:

输入: "{[]}"
输出: true

Related Topics

栈

字符串

题目解析

• 本题是一道模拟题

不确定性

方法一：栈模拟法

分析

• 当我们在字符串中遇到左边括号先保留，遇到右边括号则去找与之最近的左边括号配对，然后删去
• 如果字符串内，所有右边括号都能找到与之配对的左边括号，就表示该字符串有效

思路

• 建立一个map，对大中小三种类型的括号进行映射
• 建立栈，对于左边括号直接入栈，对于右边括号，如果栈顶有元素能与之配对，则出栈
• 遍历字符串s，若遍历完成后栈中没有元素，则表示所有的右边括号都能有左边括号与之配对，则字符串有效，反之无效

注意

• 在使用栈的top()函数获取栈顶元素前，一定要先判断栈内是否存在元素

知识点

• 栈
• map
• 字符串的遍历

复杂度

• 时间复杂度 O(n)
• 空间复杂度 O(n)

代码

bool isValid(string s) {
       map<char, char> m;
        m.insert(pair<char, char>(')', '('));
        m.insert(pair<char, char>(']', '['));
        m.insert(pair<char, char>('}', '{'));

        stack<char> stk;
        for (string::size_type i = 0; i < s.size(); i++){
            if ((s[i] == ')' || s[i] == ']' || s[i] == '}') && (!stk.empty() && stk.top() == m[s[i]])){
                stk.pop();
                continue;
            }
            else{
                stk.push(s[i]);
            }
        }
        return stk.empty();
    }

方法二：[算法名称]

分析

思路

注意

知识点

复杂度

代码

//

相关题目

• https://leetcode-cn.com/problems/binary-tree-inorder-traversal/