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:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.
  3. Every close bracket has a corresponding open bracket of the same type.

 

Example 1: 

Input: s = "()"
Output: true

Example 2: 

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

Example 3: 

Input: s = "(]"
Output: false

 

Constraints:

  • 1 <= s.length <= 104
  • s consists of parentheses only '()'.

解答

看好规则，用个stack处理。 

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
26
27
28
class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        string l={"({["},r={")}]"};
        for (auto c:s){
            if (l.find(c)!=string::npos){

                st.push(c);
            }
            else{
                if (st.size()==0){
                    return false;
                }
                if (l[r.find(c)]==st.top()){
                    st.pop();
                }
                else{
                    return false;
                }
            }
        }
        if (st.size()){
            return false;
        }
        return true;
    }
};

Complexity

  • Time: \(O(n)\)
  • Space: \(O(n)\)

题外话

注意string::nops是unsign_int里最大的正数，所以直接用变量名就好了，不要自己写个-1。