Very slow, but very intuitive solution


  • 0
    C

    Very slow, but very intuitive solution. In the real industrial, you don't have to always achieve the optimal efficency.
    Simple try all the permutations of operations, and form different equations with the permutations.

    from itertools import permutations
    import re
    
    
    def formEquationByPerm(perm, entities):
        seq = list(perm)
        for i in xrange(0, len(seq)):
            seq[i] = 2*seq[i] + 1
        
        seq.reverse()
        currEqua = entities
        
        while len(seq) > 1:
            opIdx = seq.pop()
            num1 = currEqua[opIdx-1]
            num2 = currEqua[opIdx+1]
            op = currEqua[opIdx]
            
            currEqua = currEqua[:opIdx-1] + ['('+num1+op+num2+')'] + currEqua[opIdx+2:]
            seq = [x-2 if x > opIdx else x for x in seq]
        equation = ''.join(currEqua)
        return equation
    
    
    class Solution(object):
        def diffWaysToCompute(self, input):
            """
            :type input: str
            :rtype: List[int]
            """
            entities = re.split('(\+|\*|-)', input)
            
            nPlus = entities.count('+')
            nMul = entities.count('*')
            nSub = entities.count('-')
            totalOps = nPlus + nMul + nSub
            
            equations = set()
            for perm in permutations(range(0, totalOps)):
                equations.add(formEquationByPerm(perm, entities))
                
            results = []
            for equation in equations:
                results.append(eval(equation))
                
            return results
                    
    

Log in to reply
 

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