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.
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⁴
s consists of parentheses only '()[]{}'.

Click to open Hints

Use a stack of characters.
When you encounter an opening bracket, push it to the top of the stack.
When you encounter a closing bracket, check if the top of the stack was the opening for it. If yes, pop it from the stack. Otherwise, return false.

Solution:

PythonJava

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for i in s:
            if i in ["(", "[", "{"]:
                stack.append(i)
            elif i == ")" and (stack == [] or stack.pop() != "("):
                return False
            elif i == "]" and (stack == [] or stack.pop() != "["):
                return False
            elif i == "}" and (stack == [] or stack.pop() != "{"):
                return False
        return stack == []

java

import java.util.Stack;

class Solution {
  public boolean isValid(String s) {
    if (s.length() < 2)
      return false;

    Stack<Character> stack = new Stack<>();

    for (char ch : s.toCharArray()) {
      if (ch == '(' || ch == '[' || ch == '{')
        stack.push(ch);
      else if (ch == ')' && (stack.isEmpty() || stack.pop() != '('))
        return false;
      else if (ch == ']' && (stack.isEmpty() || stack.pop() != '['))
        return false;
      else if (ch == '}' && (stack.isEmpty() || stack.pop() != '{'))
        return false;
    }

    return stack.isEmpty();
  }
}

20. Valid Parentheses #

Problem Statement #

Solution: #

... #

20. Valid Parentheses

Problem Statement

Solution:

...