Fork me on GitHub

Valid Parentheses

Posted on

Description

https://leetcode.com/problems/valid-parentheses/description/

Solution

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
class Solution {
public:
    bool checkPair(char& left, char& right) {
        return (left == '{' && right == '}') || \
            (left == '[' && right == ']') || (left == '(' && right == ')');
    }
    bool checkLeft(char& item) {
        return (item == '[') || (item == '{') || (item == '(');
    }
    bool isValid(string s) {
        if (s.size() == 0) return true;
        if (s.size() % 2 || !this->checkLeft(s[0])) return false;
        int index = 1;
        stack<char> st;
        st.push(s[0]);
        while(index < s.size()) {
            if ( this->checkLeft(s[index]) ) st.push(s[index]);
            else {
                if (!this->checkPair(st.top(), s[index]) ) return false;
                st.pop();
            }
            index += 1;
        }
        return st.empty();
    }
};