20. Valid Parentheses

easy stack

Check if a string of brackets is valid.

Given a string containing just (), {}, [], determine if the input string is valid — open brackets must be closed by the same type in the correct order.

Approach

Use a stack. Push opening brackets; when encountering a closing bracket, pop and check match — O(n) time, O(n) space.

Solutions

Ruby

def is_valid(s)
  stack = []
  map = { ")" => "(", "]" => "[", "}" => "{" }
  s.each_char do |c|
    if map.key?(c)
      return false if stack.pop != map[c]
    else
      stack.push(c)
    end
  end
  stack.empty?
end

Python

def is_valid(s: str) -> bool:
    stack = []
    pairs = {")": "(", "]": "[", "}": "{"}
    for c in s:
        if c in pairs:
            if not stack or stack.pop() != pairs[c]:
                return False
        else:
            stack.append(c)
    return not stack

Go

func isValid(s string) bool {
    stack := []rune{}
    pairs := map[rune]rune{')': '(', ']': '[', '}': '{'}
    for _, c := range s {
        if open, ok := pairs[c]; ok {
            if len(stack) == 0 || stack[len(stack)-1] != open {
                return false
            }
            stack = stack[:len(stack)-1]
        } else {
            stack = append(stack, c)
        }
    }
    return len(stack) == 0
}

TypeScript

function isValid(s: string): boolean {
    const stack: string[] = [];
    const pairs: Record<string, string> = { ")": "(", "]": "[", "}": "{" };
    for (const c of s) {
        if (pairs[c]) {
            if (stack.pop() !== pairs[c]) return false;
        } else {
            stack.push(c);
        }
    }
    return stack.length === 0;
}

Elixir

defmodule Solution do
  def is_valid(s) do
    s
    |> String.graphemes()
    |> Enum.reduce_while([], fn
      c, stack when c in ["(", "[", "{"] -> {:cont, [c | stack]}
      ")", ["(" | rest] -> {:cont, rest}
      "]", ["[" | rest] -> {:cont, rest}
      "}", ["{" | rest] -> {:cont, rest}
      _, _ -> {:halt, :invalid}
    end)
    |> case do
      [] -> true
      :invalid -> false
      _ -> false
    end
  end
end