Leetcode 0020. Valid Parentheses

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.

Easy

Description

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

Solution

package String.Java;

import java.util.Stack;

public class _0020_ValidParentheses {
  /**
   * Stack
   * Analysis
   * Time Complexity: BigO(n)
   * Space Complexity: BigO(n)
   */
  public static boolean isValid(String s) {
    Stack<Character> stack = new Stack<Character>();
    for (int i = 0; i < s.length(); i++) {
      if (s.charAt(i) == '(' || s.charAt(i) == '{' || s.charAt(i) == '[') {
        stack.push(s.charAt(i));
      }
      else {
        if (stack.empty()) return false;
        char peek = stack.peek();
        if (
          (peek == '(' && s.charAt(i) == ')') ||
          (peek == '{' && s.charAt(i) == '}') ||
          (peek == '[' && s.charAt(i) == ']')) {
          stack.pop();
        }
        else return false;
      }
    }
    return stack.empty() ? true : false;
  }
}