0ms Easy C++ Solution


  • 0

    This is a classic problem of the application of stacks. The idea is, each time we meet a (, { or [, we push it to a stack. If we meet a ), } or ], we check if the stack is not empty and the top matches it. If not, return false; otherwise, we pop the stack. Finally, if the stack is empty, return true; otherwise, return false.

    The code is as follows, very straight-forward.

    class Solution {
    public:
        bool isValid(string s) {
            stack<char> paren;
            for (int i = 0; i < s.length(); i++) {
                if (s[i] == '(' || s[i] == '{' || s[i] == '[')
                    paren.push(s[i]);
                else if (s[i] == ')' || s[i] == '}' || s[i] == ']') {
                    if (paren.empty()) return false;
                    if (!match(paren.top(), s[i])) return false;
                    paren.pop();
                }
            }
            return paren.empty();
        }
    private:
        bool match(char s, char t) {
            if (t == ')') return s == '(';
            if (t == '}') return s == '{';
            if (t == ']') return s == '[';
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.