20. Valid Parentheses

Problem statement

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

Example 1

Input: s = "()"
Output: true

Example 2

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

Example 3

Input: s = "(]"
Output: false

Constraints

• 1 <= s.length <= 10^4.

• s consists of parentheses only '()[]{}'.

Solution: Using a stack

For each character c of s:

1. If it is an open parenthesis ('(', '{', or '['), push it into the stack.

2. If it is a closed parenthesis (')', '}', or ']') but its previous character is not the corresponding open one, return false. End.

3. Otherwise (i.e. match open-closed), erase the pair.

4. Continue the process until all characters of s are visited.

5. Return true if the stack is empty, i.e. all valid pairs are erased.

Code

#include <iostream>
#include <stack>
using namespace std;
bool isValid(string s) {
    stack<char> stk;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            stk.push(c);
        } else if (stk.empty()) {
            return false;
        } else if  (c == ')' && stk.top() != '(' ||
                    c == ']' && stk.top() != '[' ||
                    c == '}' && stk.top() != '{') {
            return false;
        } else {
            stk.pop();
        }
    }
    return stk.empty();
}
int main() {
    cout << isValid("()") << endl;
    cout << isValid("(){}[]") << endl;
    cout << isValid("(]") << endl;
    cout << isValid("([)]") << endl;
}

Output:
1
1
0
0

Complexity:

• Runtime: O(N), where N = s.length.

• Extra space: O(N/2).

References

• https://leetcode.com/problems/valid-parentheses/

Thanks for reading. Feel free to share your thought about my content and check out my FREE book “10 Classic Coding Challenges”.