返回

[Leetcode]20. Valid Parentheses(C++)

题目描述

题目链接:20. Valid Parentheses

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

  • Open brackets must be closed by the same type of brackets.
  • Open brackets must be closed in the correct order.

例子

例子 1

Input: s = "()" Output: true

例子 2

Input: s = "()[]{}" Output: true

例子 3

Input: s = "(]" Output: false

例子 4

Input: s = "([)]" Output: false

例子 5

Input: s = "{[]}" Output: true

Follow Up

Note

Constraints

  • 1 <= s.length <= 10^4
  • s consists of parentheses only '()[]{}'.

解题思路

这道题可以用栈来解。首先建立一个哈希表记录左右括号之间的对应的关系。然后从头遍历字符串,遇到左括号压入栈中,遇到右括号时有三种情况:

  • 栈为空,表示当前左边没有左括号,或者所有左括号都匹配了,所以返回 false
  • 栈顶为对应的左括号,此时可以用于匹配当前右括号。将其弹出,继续遍历
  • 栈顶为不对应的左括号,表示最近的没匹配的左括号不能匹配,类似于 [) 返回 false

除此之外在最开始可以做个长度判断,如果是奇数可以直接返回 false,代码如下:

#include <string>
#include <stack>
#include <unordered_map>

class Solution {
public:
    bool isValid(std::string s) {

        if (s.length() % 2 == 1) return false;

        std::stack<char> stk;
        std::unordered_map<char, char> pairs ({
            {'(', ')'},
            {'[', ']'},
            {'{', '}'}
        });

        for (int i = 0; i < s.length(); i++) {
            if (pairs.count(s[i])) {
                stk.push(s[i]);
            } else {
                if (stk.empty() || s[i] != pairs[stk.top()]) return false;
                stk.pop();
            }
        }

        return stk.empty();
    }
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

GitHub 代码同步地址: 20.ValidParentheses.cpp

其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions

Built with Hugo
Theme Stack designed by Jimmy