Valid Parentheses

Problem

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

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

Constraints

• 1 <= s.length <= 104
• s consists of parentheses only '()[]{}'.

Solution

The problem Valid Parentheses can be solved using a stack to keep track of last open bracket.

Implementation

class Solution
{
  public:
    bool isValid(string s)
    {
        stack<char> bracket;
        map<char, char> match = {
            {')', '('},
            {'}', '{'},
            {']', '['},
        };

        for (int i = 0; i < s.length(); i++)
        {
            if (s[i] == '(' || s[i] == '{' || s[i] == '[')
                bracket.push(s[i]);
            else
            {
                if (bracket.empty() || bracket.top() != match[s[i]])
                    return false;
                bracket.pop();
            }
        }

        return bracket.empty();
    }
};