Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Balanced Parentheses (hard)

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 2 years ago

Hey,

the constraints for this are: 1 <= n <= 8

Yet, one of the test cases is n = 0 :)

A

Anonymous

· 2 years ago

It is most common way to solve this problem.

A

Anonymous

· 2 years ago

class Solution:
  def generateValidParentheses(self, num):
   
    def backtrack(result, combo, left_count, right_count):
      
      if len(combo) == 2 * num:
        result.append(combo)
        return
      
      if left_count < num:
        backtrack(result, combo + '(', left_count + 1, right_count)
      
      if right_count < left_count:
        backtrack(result, combo + ')', left_count, right_count + 1)
    
    result = []
    backtrack(result, '', 0, 0)
    return result
A

Anonymous

· 4 years ago

At each step, isn't it simpler to just add the pair of parentheses by either enclosing or appending to the previous combinations? e.g. Step 1: () Step 2: ()() (()) Step 3: ()()(), (()()) (())(), ((())) I believe the string operations would cost the same amount of time as well, so I don't think this solution compromises on any space-time efficiency.

Show 1 reply

Reading Progress

0%

Vote for new content