[LeetCode] 0020 Valid Parentheses

Valid Parentheses

LeetCode - 0020 Valid Parentheses (Easy)
https://leetcode.com/problems/valid-parentheses/

Problem Description

Given a string 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.

Note that an empty string is also considered valid.

Example 1:

Input: "()"
Output: true

Example 2:

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

Example 3:

Input: "(]"
Output: false

Example 4:

Input: "([)]"
Output: false

Example 5:

Input: "{[]}"
Output: true

Solution

Stack

class Solution {
public:
    bool isValid(string s) {
        std::stack<char> pStack;
        for(const auto& c : s){
            switch(c){
                case '{':
                    pStack.push('}');
                    break;
                case '[':
                    pStack.push(']');
                    break;
                case '(':
                    pStack.push(')');
                    break;
                default:
                    if(pStack.size() == 0 || c != pStack.top())
                        return false;
                    else
                        pStack.pop();
            }
        }
        return (pStack.size() == 0) ? true : false;
    }
};

• Time complexity is O(n) because we need to go through evey character in the given string and push and pop operations on a stack take O(1) time
• Space complexity is O(n)