LeetCode 20 Valid Parentheses Elixir solution

LeetCode problem link: 20. Valid Parentheses

You can find the problem description, deep-dive explanation, and solutions in C++, Java, JS, TS and Python programming languages supported by LeetCode here

LeetCode 20. Valid Parentheses: short description of the solution

Elixir does not have a built-in mutable stack, so we can use a list as a stack. When we find an opening bracket, we add it to the head of the list with [char | stack], which takes O(1) time. When we find a closing bracket, we compare it with the opening bracket at the top of the stack. If they match, we remove the top element and continue recursively. If they do not match, or the stack is empty, the string is invalid. After processing the entire string, the stack must be empty.

Patterns | Techniques | Data Structures

recursion
Stack - data structure
Bracket Matching - technique

Complexity

Time complexity: O(n) - each character is processed once.
Space complexity: O(n) - in the worst case, the list used as a stack can contain up to n opening brackets. The recursion is tail-recursive, so it does not add O(n) recursive call stack space.

! Elixir's pattern matching makes the bracket checks especially compact: for example, validate([?) | rest], [?( | stack]) only matches when the current character is ) and the top of the stack is (.

LeetCode 20. Valid Parentheses: Elixir solution

defmodule Solution do
  @spec is_valid(s :: String.t()) :: boolean
  def is_valid(s) do
    s
    |> String.to_charlist()
    |> validate([])
  end

  # All characters were processed.
  # The string is valid only if the stack is empty.
  defp validate([], []), do: true
  defp validate([], _stack), do: false

  # Push opening brackets onto the stack.
  defp validate([char | rest], stack) when char in [?(, ?{, ?[] do
    validate(rest, [char | stack])
  end

  # Match closing brackets with the top of the stack.
  defp validate([?) | rest], [?( | stack]), do: validate(rest, stack)
  defp validate([?} | rest], [?{ | stack]), do: validate(rest, stack)
  defp validate([?] | rest], [?[ | stack]), do: validate(rest, stack)

  # No matching opening bracket exists.
  defp validate(_chars, _stack), do: false
end