Leetcode 2232. Minimize Result by Adding Parentheses to Expression

题目

解法

暴力解，遍历左括号和右括号可能位置的所有组合，返回能找到的最小组合

class Solution:def minimizeResult(self, expression: str) -> str:# print(len(expression[:0]))left_num,right_num = expression.split('+')[0],expression.split('+')[1]min_res = 2147483647start = Noneend = Nonefor i in range(len(left_num)):for j in range(1,len(right_num)+1):part1 = left_num[:i]if len(part1) == 0:part1 = 1else:part1 = int(part1)part2 = int(left_num[i:])part3 = int(right_num[:j])part4 = right_num[j:]if len(part4) == 0:part4 = 1else:part4 = int(part4)tmp_res = part1 * (part2 + part3) * part4if min_res > tmp_res:min_res = tmp_resstart = iend = jmin_res = tmp_res# print(part1,part2,part3,part4,i,j)# print(min_res)if start != None and end != None:return left_num[:start] + '(' + left_num[start:] + '+' + right_num[:end] + ')' + right_num[end:]return '(' + expression + ')'

时间复杂度：O(n*n)
空间复杂度：O(n)，来源于left_num和right_num的表达
优化·：1. 可以单独写一个将字符串转化为最终结果的函数，增加代码可读性；2.可以直接会expression进行循环，省去left_num和right_num，将空间复杂度降为O(1)