Recursion for Coding Interviews in Python/

...

/

Solution Review: Balance Parenthesis

Solution Review: Balance Parenthesis

This review provides a detailed analysis of the solution to determine whether or not an array contains balanced parenthesis.

We'll cover the following...

Solution: Using Recursion

Press + to interact
def balanced(testVariable, startIndex = 0, currentIndex = 0) :
  # Base case1 and 2
  if startIndex == len(testVariable) : 
    return currentIndex == 0
  # Base case3
  if currentIndex < 0 : # A closing bracket did not find its corresponding opening bracket
    return False
  # Recursive case1
  if testVariable[startIndex] == "(" : 
    return  balanced(testVariable, startIndex + 1, currentIndex + 1)
  # Recursive case2
  elif testVariable[startIndex] == ")" : 
    return  balanced(testVariable, startIndex + 1, currentIndex - 1)
# Driver Code
testVariable = ["(", "(", ")", ")", "(", ")"]
print(balanced(testVariable))

Explanation

Our task is to read an array of parentheses from left to right and decide whether the symbols are balanced.

To solve this problem, notice that the most recent opening parenthesis must match the following closing parenthesis. The first opening bracket processed will be saved until the very last bracket is processed to find its corresponding closing bracket.

Closing brackets match opening brackets in the reverse order of their appearance, meaning that they match from the inside out. This is a clue that recursion can be used to solve this problem.

Let’s investigate the code snippet above.

The two variables startIndex and currentIndex are important to note. startIndex traverses the whole array. In each recursive call, it moves to the next element in the array. It also checks whether or not we have reached the end of the array.

The currentIndex examines if each opening bracket has a corresponding closing bracket. If we encounter a closing ...