[LeetCode] 20. Valid Parentheses

Table of Contents

Description

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

Example 4:

Input: s = "([])"
Output: true

Constraints:

• $1 \leq s.length \leq 10^4$
• s consists of parentheses only '()[]{}'.

Approach

We use a stack to track opening brackets. As we iterate through the string, each opening bracket is pushed onto the stack, and for every closing bracket encountered, we check if it matches the last opening bracket by popping from the stack; if not, the string is invalid. If the stack is empty at the end, all brackets are properly closed.

Solution

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
  // If the string length is 0, return true since an empty string is valid
  if (!s.length) return true;

  // Define a mapping for corresponding parentheses
  const PARENTHES_MAP = {
    ")": "(",
    "]": "[",
    "}": "{",
  };
  const stack = [];

  // Iterate through each character in the string
  for (const char of s) {
    // If the character is a closing parenthesis
    if (PARENTHES_MAP[char]) {
      // Check if the last opening parenthesis in the stack matches
      if (stack.pop() !== PARENTHES_MAP[char]) return false;
    } else {
      // If it's an opening parenthesis, push it onto the stack
      stack.push(char);
    }
  }
  // If the stack is empty, all opening parentheses have matching closing ones, return true
  return stack.length === 0;
};

Complexity Analysis

Time Complexity

The time complexity of this algorithm is $O(n)$, where n is the length of the input string s. This is because we iterate through each character in the string once.

Space Complexity

The space complexity is $O(n)$ in the worst case, where all characters are opening parentheses. In this case, we would need to store all of them in the stack.