[Python] Long Yet Easy to Understand Solution Using DFS


  • 0
    4

    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
    

    '''


Log in to reply
 

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