Problem overview

We are given a string s containing only the characters '(', ')', '{', '}', '[', and ']'.

We need to determine if the input string is valid or not. A string is valid if:

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

LeetCode - Valid Parentheses

Examples

Valid

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

Invalid

Input:  s = "([)]"
Output: false

Dry run

Step through the algorithm character by character. Type your own bracket string to test it.

Stack (top → bottom)
empty

Solution — Stack

Intuition

  • Use a stack to store opening brackets.
  • When we encounter a closing bracket, check if the stack is empty — if it is, the string is invalid.
  • If the top of the stack is not the matching opening bracket, the string is invalid.
  • After processing all characters, the string is valid only if the stack is empty.

Code (C++)

 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 isValid(string s) {

        stack<char> st;

        for (auto it : s) {

            if (it == '(' || it == '[' || it == '{') {
                st.push(it);
            } 
            else {
                if (st.empty()) return false;

                char top = st.top();
                st.pop();

                if (it == ')' && top != '(') return false;
                if (it == '}' && top != '{') return false;
                if (it == ']' && top != '[') return false;
            }
        }

        return st.empty();
    }
};

Time and Space Complexity

Time: O(n) Space: O(n) #Stack