[LeetCode Road] Valid Parentheses - Solution/C++

20. Valid Parentheses

Question:

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.

Example:

Input: s = "()"
Output: true

Input: s = "()"
Output: true

Input: s = "(]"
Output: false

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

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

Constraints:

1 <= s.length <= 10^4

s consists of parentheses only '()'.

Source code

Version 1

Idea:
Use map<key, value> to declare the characters. Notice: a string will be process is left parenthese, so these can be used as a value. Then, I can use key-value to do match when right parenthese is processed.

I get each characters to check whether it is unrecorded or equal st.top() or not. If it is true, this character be added at the top of the stack. On the contrary, delete the top most element of the stack. Finally, ues st.empty() to return whether the stack is empty.
P.S. Stack is LIFO(Last In First Out).

Time complexity: O(l)
Space complexity: O(h + l)

class Solution {
public:
    bool isValid(string s) {
        if(s.length() == 1) return false;
        map<char, char>  match{{'(', ')'}, {'{','}'},{'[',']'}};
        stack<char> st;
        for(const char c:s){
            if(st.empty() || c != st.top()){
                st.push(match[c]);
            }else{
                st.pop();
            }
        }
        return st.empty();
    }
};

Version 2

Idea:
Get rid of using map or unordered_map, adopt switch statement to implement it.

Time complexity: O(l)
Space complexity: O(l)

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        for(char &c : s){
            switch(c){
                case '(': st.push(')'); break;
                case '{': st.push('}'); break;
                case '[': st.push(']'); break;
                default: 
                    if(st.empty() || c != st.top()) return false;
                    else st.pop();
            }
        }
        return st.empty();
    }
};