Very slow, but very intuitive solution

  • 0

    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
        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:
            return results

Log in to reply

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