Valid Parentheses

  # 1. Valid Parentheses
  # Problem: Determine if the input string of brackets is valid.
  # Input: "()[]{}", Output: true
  # Input: "(]", Output: false
  # Time Complexity: O(n)
  def valid_parentheses(s)
    stack = []
    map = { ")" => "(", "}" => "{", "]" => "[" }
    s = s.gsub(/[^()\[\]{}]/, "") # remove all non parentheses characters
    s.each_char.with_index do |char, idx|
      if map.values.include?(char)
        stack.push(char)
        puts "Stack after push #{idx}: #{stack.inspect}"
      elsif map.keys.include?(char)
        top = stack.pop
        puts "Stack after pop #{idx}: #{stack.inspect} (popped: #{top})"
        return false if top != map[char]
      end
    end
    stack.empty?