Valid Parentheses | Problems

Given a string containing only the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

A string is valid when every opening bracket has a matching closing bracket of the same type, and brackets close in the correct order. An empty string is considered valid.

Examples

Input: s = "()"
Output: true

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

Input: s = "(]"
Output: false

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

Input: s = "{[]}"
Output: true

Constraints

1 <= s.length <= 10^4
s consists of parentheses characters only.

Sample Input

s = "()[]{}"

Sample Output

true

Constraints

1 <= s.length <= 10^4
s consists of '()[]{}' only

Test Cases

Case 1

Args: ["()[]{}"] Expected: true

Topics

String Hash Table

Use a stack. Push every opening bracket. When a closing bracket appears, check that the stack is non-empty and the top matches. If the stack is empty at the end, all brackets were properly matched.

function isValid(s) {
  const stack = [];
  const pairs = { ')': '(', '}': '{', ']': '[' };

  for (const ch of s) {
    if (ch === '(' || ch === '{' || ch === '[') {
      stack.push(ch);
    } else {
      if (stack.length === 0 || stack[stack.length - 1] !== pairs[ch]) {
        return false;
      }
      stack.pop();
    }
  }

  return stack.length === 0;
}

Time: O(n) — single pass through the string. Space: O(n) — stack holds at most n/2 elements.

Saved in this browser only. Private to you.