5
\$\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\$
2
  • 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, 2016 at 19:36
  • \$\begingroup\$ Nice catch! Updated my answer. \$\endgroup\$
    – Nakilon
    Apr 20, 2016 at 11:58

3 Answers 3

5
\$\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\$
5
  • \$\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, 2016 at 14:54
  • \$\begingroup\$ This one was failing:[[ \$\endgroup\$
    – Nakilon
    Apr 20, 2016 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, 2016 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, 2016 at 10:19
  • \$\begingroup\$ True, although technically you could do end.empty?--although that's ugly. \$\endgroup\$
    – Mohamad
    Apr 25, 2016 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\$
0
\$\begingroup\$

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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Welcome to Code Review! You have presented an alternative solution, but haven't reviewed the code. Please edit to show what aspects of the question code prompted you to write this version, and in what ways it's an improvement over the original. It may be worth (re-)reading How to Answer. \$\endgroup\$ Feb 11 at 8:11
  • 1
    \$\begingroup\$ It's also wrong - it returns true for )( which is not balanced. \$\endgroup\$ Feb 11 at 8:12

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.