Python, Exhaustive Approach with Explanation


  • 0

    Let's find the indices of the N-1 divisions that take place. For example, in [1000, 100, 10, 2], the divisions are path = [1, 1, 0] (Note that subsequent indices are relative to the smaller array.)

    Example:
    [1000, 100, 10, 2]: divide at 1
    [1000, (100/10), 2]: divide at 1
    [1000, (100/10/2)]: divide at 0
    path = [1, 1, 0]

    To find this path, we'll consider i to be the location of the next division. Then all the stuff before A[i] is divided in the normal way, and then A[i] is divided by A[i+1], as in the expression flat(A[:i]) + flat(A[i:i+2]) + A[i+2:]. We'll take the path with the max value.

    Once we found the path, to form the string, we need to ignore redundant parentheses. We do this by converting repeated values to a parentheses range "(i, j)". For example, [1, 1, 0] will convert to [(1, 3), (0, 1)]. By "(1, 3)", we mean that we should parenthesize the elements from indices 1 to 3. Because of the order that we've considered the path, repeated values will occur iff we are doing a "redundant" division from left to right of adjacent elements. We then convert our token list to the new values: for example, the first move "(1, 3)" leaves us with the token list ['1000', '(100/10/2)'].

    def optimalDivision(self, A):
        tokens = map(str, A)
        A = map(float, A)
        
        def flat(A):
            if not A: return []
            head = A[0]
            for x in A[1:]:
                head /= x
            return [head]
        
        def search(A, path = []):
            if len(A) == 1: return A[0], path
            return max( search( flat(A[:i]) + flat(A[i:i+2]) + A[i+2:], path + [i])
                        for i in xrange(len(A) - 1) )
        
        _, path = search(A)
    
        for i, v in itertools.groupby(path[:-1]):
            j = i + len(list(v))
            tokens = tokens[:i] + ['({})'.format('/'.join(tokens[i:j+1]))] + tokens[j+1:]
    
        return '/'.join(tokens)
    

Log in to reply
 

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