4
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ There's a subtle bug in my code that perhaps isn't work a new answer. At the end, instead of returning true, I should check to see if the stack is empty. \$\endgroup\$ – Mohamad Apr 19 '16 at 19:36
  • \$\begingroup\$ Nice catch! Updated my answer. \$\endgroup\$ – Nakilon Apr 20 '16 at 11:58
4
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Having added my comment re ensuring the stack is empty, I'm finding it hard to think of a scenario that this could be possible. Do you have something in mind? I found this out when one test case failed, but the source of the problem doesn't make the test cases public (which is rediculous). \$\endgroup\$ – Mohamad Apr 20 '16 at 14:54
  • \$\begingroup\$ This one was failing:[[ \$\endgroup\$ – Nakilon Apr 20 '16 at 19:52
  • \$\begingroup\$ I'm curious: Why did you use a temp variable stack instead of using each_with_object like I did? \$\endgroup\$ – Mohamad Apr 24 '16 at 11:40
  • \$\begingroup\$ @Mohamad, I guess after .chars do it would be out of the scope and I'll be unable to call .empty? on it. \$\endgroup\$ – Nakilon Apr 25 '16 at 10:19
  • \$\begingroup\$ True, although technically you could do end.empty?--although that's ugly. \$\endgroup\$ – Mohamad Apr 25 '16 at 11:13
0
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.