Valid Parentheses Easy 0 attempts
Daily LeetCode ↗

Valid Parentheses

Easy StringHash Table LeetCode

You're given a string made up exclusively of the bracket characters '(', ')', '{', '}', '[', and ']'. Figure out whether the brackets in it are properly balanced.

The string counts as valid when every opening bracket is eventually closed by the matching bracket type, and the closures happen in the right nested order. An empty string is trivially valid.

Input Format
Implement isValid(s). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

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

Example 2

Input
s = "([)]"
Output
false
Constraints
  • 0 <= s.length <= 10^4
  • s consists of '()[]{}' only.
Test Cases (2)
Case 1
Args: ["()[]{}"] Expected: true
Case 2
Args: ["([)]"] Expected: false
Topics
StringHash 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.

javascript
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.

JavaScript