LeetCode-in-All
20. Valid Parentheses
Easy
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
Example 1:
Input: s = “()”
Output: true
Example 2:
Input: s = “()[]{}”
Output: true
Example 3:
Input: s = “(]”
Output: false
Example 4:
Input: s = “([)]”
Output: false
Example 5:
Input: s = “{[]}”
Output: true
Constraints:
1 <= s.length <= 104sconsists of parentheses only'()[]{}'.
Solution
defmodule Solution do
@compliments %{
")" => "(",
"]" => "[",
"}" => "{"
}
@spec is_valid(s :: String.t) :: boolean
def is_valid(s) do
s
# charlists are easy
|> String.graphemes()
# rly gross reduce, but it is a functional way to carry our stack along.
|> List.foldl([], fn item, acc ->
case Map.get(@compliments, item) do
# Not a closer, just add it to the stack
nil -> [item | acc]
# Closer of some kind - check if the top of the stack is
# the compliment - if not, add it to the stack.
# If it is, we can drop one from the stack to clear that set.
c -> if c == List.first(acc) do
Enum.drop(acc, 1)
else
[item | acc]
end
end
end)
# If the stack is empty, then it's valid. Else, we'll
# have some junk left over from the mismatched pairs.
|> Enum.empty?()
end
end