0%

LeetCode 20. Valid Parentheses

Posted on In

题目

原题在此

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.

Example 1:

Input: s = “()”
Output: true

Example 2:

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

Example 3:

Input: s = “(]”
Output: false

Example 4:

Input: s = “([)]”
Output: false

Example 5:

Input: s = “{[]}”
Output: true

Constraints:

  • 1 <= s.length <= 104
  • s consists of parentheses only ‘()[]{}’.

解析

学过Stack这种后进先出储存结构的就知道怎么做.左括号就入栈, 右括号就看栈顶元素是否匹配. 最后看栈是否为空.

代码

c++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    bool isValid(string s) {
        std::stack<char> stack;
        for(auto c : s){
            if(c == '(' || c == '[' || c == '{') stack.push(c);
            
            if(c == ')'){
                if(!stack.empty() && stack.top() == '(') stack.pop();
                else return false;
            }

            if(c == ']'){
                if(!stack.empty() && stack.top() == '[') stack.pop();
                else return false;
            }
            
            if(c == '}'){
                if(!stack.empty() && stack.top() == '{') stack.pop();
                else return false;
            }
        }
        return stack.empty();
    }
};