0020 - Valid Parentheses (Easy)

Problem Link

https://leetcode.com/problems/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.
3. Every close bracket has a corresponding open bracket of the same type.

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 '()[]{}'.

Approach 1: Stack

Stack is widely known as LIFO (last-in, first-out) data structure.

It's commonly used in undo mechanisms in text editors and compiler syntax checking for matching brackets and braces.

Parentheses/braces can be in this order '()()' or '(())', since the last open '(' brace next sequence could be either ')' or '(' another open brace to nested open braces.

If the input has any of the open '(' or '{' or '[' we can push onto a stack. If any close braces/parentheses comes then validate with last inserted character which is on the stack pop, should match corresponding open braces/paranetheses.

Time Complexity: $O(n)$, where $n$ - # of characters in the string

Space complexity: $O(n)$

Java

Written by @vigneshshiv

class Solution {
    public boolean isValid(String s) {
        if (Objects.isNull(s) || s.isEmpty() || s.length() < 2) {
            return false;
        }
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (Objects.equals(c, '(') || Objects.equals(c, '[') || Objects.equals(c, '{')) {
                stack.push(c);
            } else {
                if (stack.isEmpty()) {
                    return false;
                }
                char last = stack.pop();
                if (Objects.equals(c, ')') && !Objects.equals(last, '(')) {
                    return false;
                }
                if (Objects.equals(c, ']') && !Objects.equals(last, '[')) {
                    return false;
                }
                if (Objects.equals(c, '}') && !Objects.equals(last, '{')) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

Python

Written by @vale-c

class Solution:
    def isValid(self, s: str) -> bool:
        # if string is empty or has only one character
        if not s or len(s) < 2:
            return False
        stack = []
        # iterate over the string
        for c in s:
            # if the character is an opening bracket
            if c in ['(', '[', '{']:
                # push it to the stack
                stack.append(c)
            else:
                # if the stack is empty there is no opening bracket to match
                if not stack:
                    return False
                last = stack.pop()
                # if the character is a closing bracket and the last element
                # in the stack is not the corresponding opening bracket
                if c == ')' and last != '(':
                    return False
                if c == ']' and last != '[':
                    return False
                if c == '}' and last != '{':
                    return False
        # if the stack is empty it means
        # that all the brackets were matched
        return not stack

JavaScript

Written by @vale-c

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    // if string is empty or has only one character
    if (!s || s.length < 2) {
        return false;
    }
    let stack = [];
    // iterate over the string
    for (let c of s) {
        // if the character is an opening bracket
        if (c === '(' || c === '[' || c === '{') {
            // push it to the stack
            stack.push(c);
        } else {
            // if the stack is empty there is no opening bracket to match
            if (!stack.length) {
                return false;
            }
            let last = stack.pop();
            // if the character is a closing bracket and the last element
            // in the stack is not the corresponding opening bracket
            if (c === ')' && last !== '(') {
                return false;
            }
            if (c === ']' && last !== '[') {
                return false;
            }
            if (c === '}' && last !== '{') {
                return false;
            }
        }
    }
    // if the stack is empty it means
    // that all the brackets were matched
    return !stack.length;
};

C++

Written by @vale-c

class Solution {
public:
    bool isValid(string s) {
        // if string is empty or has only one character
        if (s.empty() || s.length() < 2) {
            return false;
        }
        stack<char> stack;
        // iterate over the string
        for (char c : s) {
            // if the character is an opening bracket
            if (c == '(' || c == '[' || c == '{') {
                // push it to the stack
                stack.push(c); 
            } else {
                // if the stack is empty there is no opening bracket to match
                if (stack.empty()) {
                    return false;
                }
                char last = stack.top();
                stack.pop();
                // if the character is a closing bracket and the last element 
                // in the stack is not the corresponding opening bracket
                if (c == ')' && last != '(') { 
                    return false;
                }
                if (c == ']' && last != '[') {
                    return false;
                }
                if (c == '}' && last != '{') {
                    return false;
                }
            }
        }
        // if the stack is empty it means
        // that all the brackets were matched
        return stack.empty();
    }
};