Make writing a habit together! This is the 13th day of my participation in the “Gold Digging Day New Plan · April More Text Challenge”. Click here for more details.

describe

You are given a 0-indexed string expression of the form “+” where and 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. The left parenthesis must be added to the left of ‘+’ and the right parenthesis must be added to the right of ‘+’.

Return expression after adding a pair of parentheses such that expression evaluates to the smallest possible value. If there are multiple answers that yield the same result, return any of them.

The input has been generated such that the original value of expression, and the value of expression after adding any pair of parentheses that meets the requirements fits within a signed 32-bit integer.

Example 1:

Input: expression = "247+38"
Output: "2(47+38)"
Explanation: The expression evaluates to 2 * (47 + 38) = 2 * 85 = 170.
Note that "2(4)7+38" is invalid because the right parenthesis must be to the right of the '+'.
It can be shown that 170 is the smallest possible value.
Copy the code

Example 2:

Input: expression = "12+34"
Output: "1(2+3)4"
Explanation: The expression evaluates to 1 * (2 + 3) * 4 = 1 * 5 * 4 = 20.
Copy the code

Example 3:

Input: expression = "999+999"
Output: "(999+999)"
Explanation: The expression evaluates to 999 + 999 = 1998.
Copy the code

Note:

3 <= expression.length <= 10 expression consists of digits from '1' to '9' and '+'. expression starts and ends with digits. expression contains exactly one '+'. The original value of expression, and the value of expression after adding any pair of parentheses that meets the requirements fits within a signed 32-bit  integer.Copy the code

parsing

Given a zero-indexed string expression of the form “+”, where and represent positive integers.

When we add a pair of parentheses to an expression, the expression is a valid mathematical expression, which is essentially the addition of the parentheses, and the multiplication of the parentheses, which requires us to compute the string that corresponds to the smallest possible value.

Because a bunch of parentheses can be added in different places, any one of them is returned if there are more than one answer.

In fact, this problem is about the understanding and violent solution of the problem. I used violence to solve the problem in the competition, because the maximum length of expression in the restricted conditions is 10, and the violent solution can save a lot of time for thinking during the competition, and also can AC. But after the game I went to the forums to find a simpler solution, only to find a violent solution [face covering], which also lost the motivation to optimize the code.

My idea is actually very simple, although the code is a bit long, but very easy to understand:

  • Extract the two numbers in expression as A or B respectively
  • Use two variables, I and j, to represent the position of the open parenthesis at A and the close parenthesis at B for A double loop
  • Because “(” can cut A into two parts preA and tailA (of course, if preA is empty, it will be assigned 1 because its position will be multiplied; If tailA is empty, give it a value of 0 because its position is being added); B can be cut into two parts preB and tailB (same as above for empty case)
  • Computes preA*(tailA + preB)*tailB and updates the final result string result if it is less than the current MX
  • Return result at the end of the loop

N1 and N2 are two digits, respectively. The time complexity is O(N1 x N2), and the space complexity is O(N1 + N2).

answer

class Solution(object):
    def minimizeResult(self, expression):
        """
        :type expression: str
        :rtype: str
        """
        A,B = expression.split('+')
        n1 = len(A)
        n2 = len(B)
        mx = float('inf')
        result = ''
        for i in range(n1):
            preA = A[:i]
            if not preA:
                preA = 1
            tailA = A[i:]
            if not tailA:
                tailA = 0
            for j in range(1, n2+1):
                preB = B[:j]
                if not preB:
                    preB = 0
                tailB = B[j:]
                if not tailB:
                    tailB = 1
                tmp = int(preA)*(int(tailA) + int(preB))*int(tailB)
                if mx > tmp:
                    mx = min(mx, tmp)
                    result  = A[:i] + '(' + A[i:] + '+' + B[:j] + ')' + B[j:]
        return result		
Copy the code

The results

124/124 Test cases passed. Status: Accepted Runtime: 34 MS Memory Usage: 13.6 MBCopy the code

The original link

Leetcode.com/contest/wee…

Your support is my biggest motivation