# [Python] Long Yet Easy to Understand Solution Using DFS

• Who says the shorter ones have to be the better ones?
Here I present a long yet easy to understand solution using DFS.
P.S. This solution is based on my solution for the "eight queens problem".

My solution has 3 parts:
entry: to kick start and control the strings' length and return results;
validator feeder: feed the validator with the new and longer strings;
validator: validate a string.

'''

``````def generateParenthesis(self, n):
'''Entry, control the string length'''
# stores valid lays
result = []

valid_sequences = self.validator_feeder('', n)

current_length = 1

while current_length < 2 * n:
for string in valid_sequences:
if len(string) == current_length:
valid_sequences += self.validator_feeder(string, n)
current_length += 1

for i in range(len(valid_sequences) - 1, -1, -1):
s = valid_sequences[i]
if len(s) < 2 * n:
break
result.append(s)

return result

def validator_feeder(self, string, n):
'''
generate new strings that are longer the
string[:index] is validated
'''

# stores valid lays (until index)
result = []
for parentheses in '()':
new_string = string + parentheses
if self.validate(new_string, n):
result.append(new_string)

# index in result is validated here
return result

def validate(self, string, n):
'''returns if the current string is valid'''

index = len(string) - 1
if index == 0:
return True if string == '(' else False
# if index > 5: return False

validated_string = string[:index]
current_item = string[index]
lefty_count = validated_string.count('(')
righty_count = validated_string.count(')')

# "(" and ")" must be no more than 3
if current_item == '(':
lefty_count += 1
else:
righty_count += 1

if lefty_count > n or righty_count > n:
return False

# lefties must not less than righties
if lefty_count < righty_count:
return False

return True
``````

'''

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.