Balanced parenthesis in Ruby

Question

I'm solving the "Balanced Parenthesis" problem in Ruby, and I came up with this solution.

def balanced?(string)
  return false if string.length.odd?

  pairs = { '{' => '}', '[' => ']', '(' => ')' }

  string.chars.each_with_object([]) do |bracket, stack|
    if pairs.keys.include?(bracket)
      stack << bracket
    elsif pairs.values.include?(bracket)
      return false unless pairs[stack.pop] == bracket
    else
      return false
    end
  end

  true
end

The first check is for the length of the string: If it's odd, the can't be balanced.

I then iterate over the chars of the string:

1. If I find an opening bracket, I add it to an array.
2. If I find a closing bracket, I remove the last element from the array and check if the brackets are a pair.
3. If I find neither an opening or a closing bracket, the string must be invalid.

Are there any edge cases I'm missing? Also, this doesn't seem efficient: First, there's an added dictionary. Second, there is a linear search on each iteration to check either the keys or the values of the dictionary. There's an \$O(n)\$ on the array resulting from the string, as well, but I'm not sure if we can avoid this.

Answer 1

To eliminate nested loop you may apply regex checking for invalid symbol from the start -- it would be O(n) + O(n) = O(n):

def balanced? string
  return false if string.length.odd?
  return false if string =~ /[^\[\]\(\)\{\}]/

  pairs = { '{' => '}', '[' => ']', '(' => ')' }

  stack = []
  string.chars do |bracket|
    if expectation = pairs[bracket]
      stack << expectation
    else
      return false unless stack.pop == bracket
    end
  end

  stack.empty?
end

Answer 2

Assuming it's possible to check each pair separately:

def is_balanced(opener, closer, str)
  cnt = 0
  adds = {opener => 1, closer => -1}
  pars = str.chars.select{|c| [opener, closer].include? c }
  pars.each{ |c| cnt += adds[c]; return false if cnt < 0 }
  cnt == 0
end

def is_balanced2(str)
  [['(', ')'], ['[', ']'], ['{', '}']].map{ |ps| is_balanced(*ps, str) }.all?
end

Answer 3

Constant Time solution, assuming you know the paren chars:

    def is_valid(str)
        characters = [
            '(', ')',
            '{', '}', 
            '[', ']',
        ]
       
        if str.count(characters[0]) != str.count(characters[1])
            return false
        end
    
        if str.count(characters[2]) != str.count(characters[3])
            return false
        end
    
        if str.count(characters[4]) != str.count(characters[5])
            return false
        end
    
        true
    end

Its beautifully simple.