Minimize Result by Adding Parentheses to Expression — LeetCode 2232 Python Solution

The problem

You are given a 0-indexed string expression of the form "<num1>+<num2>" where <num1> and <num2> represent positive integers. Add a pair of parentheses to expression such that after the addition of parentheses, expression is a valid mathematical expression and evaluates to the smallest possible value.

Example

Input

expression = "247+38"

Output

"2(47+38)"

Explanation

The expression evaluates to 2 * (47 + 38) = 2 * 85 = 170.

Python solution

class Solution:
    def minimizeResult(self, expression: str) -> str:
        l, r = expression.split("+")
        m, n = len(l), len(r)
        mi = inf
        ans = None
        for i in range(m):
            for j in range(n):
                c = int(l[i:]) + int(r[: j + 1])
                a = 1 if i == 0 else int(l[:i])
                b = 1 if j == n - 1 else int(r[j + 1 :])
                if (t := a * b * c) < mi:
                    mi = t
                    ans = f"{l[:i]}({l[i:]}+{r[: j + 1]}){r[j + 1:]}"
        return ans

Complexity

Pattern: Hash Map

Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 2232. Minimize Result by Adding Parentheses to Expression is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.

The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.

Related problems