Valid Parentheses

Problem

You are given a string s consisting of the following characters: '(', ')', '{', '}', '[' and ']'.

The input string s is valid if and only if:

1. Every open bracket is closed by the same type of close bracket.
2. Open brackets are closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

Return true if s is a valid string, and false otherwise.

Examples

Example 1:

Input: s = "[]"

Output: true

Example 2:

Input: s = "([{}])"

Output: true

Example 3:

Input: s = "[(])"

Output: false

Constraints

• 1 <= s.length <= 1000

You should aim for a solution with O(n) time and O(n) space, where n is the length of the given string.

Solution

Use a vector as a stack to push open braces on. Once we read a closing brace, check if top of stack is the corresponding open brace of that type. Solution if at the end the stack is empty.

class Solution {
public:
    inline static std::unordered_map<char, char> brace_map = {
        {'{', '}'}, {'(', ')'}, {'[', ']'}
    };
    inline static std::unordered_set<char> open_braces = {'{', '(', '['};
    bool isValid(std::string_view s) {
 
        // Use a stack to push on opening braces, and pop off closing braces
        // Result is valid if stack is empty
        std::vector<char> brace_stack;
        for (const auto &c : s) {
            if (open_braces.contains(c)) {
                brace_stack.push_back(c);
            } else {
                // c is a closing brace, check if it matches top of stack
                if (!brace_stack.empty() && brace_map[brace_stack.back()] == c) {
                    brace_stack.pop_back();
                } else {
                    return false;
                }
            }
        }
 
        return brace_stack.empty();
    }
};