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:

Open brackets must be closed by the same type of brackets.
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:

If it is an open parenthesis ('(', '{', or '['), push it into the stack.
If it is a closed parenthesis (')', '}', or ']') but its previous character is not the corresponding open one, return false. End.
Otherwise (i.e. match open-closed), erase the pair.
Continue the process until all characters of s are visited.
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”.

20. Valid Parentheses

Comments

More from this blog

Leetcode 59. How To Go Around A Square Matrix In Spiral Order

Leetcode 120. How To Find The Minimum Path From Top To Bottom Of A Triangle

How To Find The Longest Substring Without Repeating Characters

How To Find The Maximal Subarray Having Distinct Elements

Common Mistakes in Coding Interviews and How to Avoid Them

Problem statement

Example 1

Example 2

Example 3

Constraints

Solution: Using a stack

Code

Complexity:

References

Command Palette

Comments

More from this blog

Problem statement

Example 1

Example 2

Example 3

Constraints

Solution: Using a stack

Code

Complexity:

References