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.
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)$

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();
    }
}

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

/**
 * @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;
};

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();
    }
};

0020 - Valid Parentheses (Easy)

Problem Link

Problem Statement

Approach 1: Stack

On this page