diff options
author | Jack Sangdahl <[email protected]> | 2025-10-01 09:45:51 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-10-01 09:45:51 -0600 |
commit | 01585d45e77abeb96336aac00896b11ad0298956 (patch) | |
tree | 13040ddfcb5ebc6cbc003af5c502b36ccc2610bf | |
parent | 9885ede0c5c6394f0196b2e7d459105d77749c07 (diff) | |
download | leetcode-01585d45e77abeb96336aac00896b11ad0298956.tar.gz leetcode-01585d45e77abeb96336aac00896b11ad0298956.zip |
2232. minimise result by addding parenthesese to expression
-rw-r--r-- | minimize_result_add_parentheses.c | 78 | ||||
-rw-r--r-- | minimize_result_add_parentheses.py | 33 |
2 files changed, 111 insertions, 0 deletions
diff --git a/minimize_result_add_parentheses.c b/minimize_result_add_parentheses.c new file mode 100644 index 0000000..a338bc0 --- /dev/null +++ b/minimize_result_add_parentheses.c @@ -0,0 +1,78 @@ +// 2232. Minimize Result by Adding Parentheses to Expression +#include "leetcode.h" + +/* + * you are given a 0-indexed string 'expression' of the form 'num1+num2' where + * 'num1' and 'num2' represent 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 multiple answers that yield the same result, return any of + * them. + */ + +void helper(char *res, char *expression, int n, int pos) { + int num = INT_MAX, l = 0, r = 0; + for (int i = 0; i < pos; i++) { + int lidx = i, a = 0, c = 0; + for (int j = lidx; j < pos; j++) { + a *= 10; + a += (expression[j] - '0'); + } + for (int j = 0; j < lidx; j++) { + c *= 10; + c += (expression[j] - '0'); + } + if (!c) + c++; + for (int j = n - 1; j > pos; j--) { + int ridx = j, b = 0, d = 0; + for (int k = ridx; k > pos; k--) + b += (expression[k] - '0') * pow(10, ridx - k); + for (int k = ridx + 1; k < n; k++) { + d *= 10; + d += (expression[k] - '0'); + } + if (!d) + d++; + int ans = c * (a + b) * d; + if (ans < num) { + num = ans; + l = lidx; + r = ridx; + } + } + } + int idx = 0; + for (int i = 0; i < n + 3; i++) { + if (i == l) + res[i] = '('; + else if (i == r + 2) + res[i] = ')'; + else + res[i] = expression[idx++]; + } +} + +char *minimizeResult(char *expression) { + int n = strlen(expression), pos = 0; + for (int i = 0; i < n; i++) + if (expression[i] == '+') { + pos = i; + break; + } + char *ans = (char *)calloc(n + 3, sizeof(char)); + helper(ans, expression, n, pos); + return ans; +} + +int main() { + char *e1 = "247+38", *mr1 = minimizeResult(e1); + char *e2 = "12+34", *mr2 = minimizeResult(e2); + char *e3 = "999+999", *mr3 = minimizeResult(e3); + printf("%s\n", mr1); // expect: 2(47+38) + printf("%s\n", mr2); // expect: 1(2+3)4 + printf("%s\n", mr3); // expect: (999+999) +} diff --git a/minimize_result_add_parentheses.py b/minimize_result_add_parentheses.py new file mode 100644 index 0000000..b59eca3 --- /dev/null +++ b/minimize_result_add_parentheses.py @@ -0,0 +1,33 @@ +# 2232. Minimize Result by Adding Parentheses to Expression + +""" +you are given a 0-indexed string 'expression' of the form 'num1+num2' where +'num1' and 'num2' represent 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 multiple answers that yield the same result, return any of +them. +""" + + +class Solution(object): + def minimizeResult(self, expression): + """ + :type expression: str + :rtype: str + """ + left, right = expression.split("+") + value = lambda s: eval(s.replace("(", "*(").replace(")", ")*").strip("*")) + l = [left[0:i] + "(" + left[i:] for i in range(len(left))] + r = [right[0:i] + ")" + right[i:] for i in range(1, len(right) + 1)] + return min([i + "+" + j for i in l for j in r], key=value) + + +if __name__ == "__main__": + obj = Solution() + print(obj.minimizeResult(expression="247+38")) + print(obj.minimizeResult(expression="12+34")) + print(obj.minimizeResult(expression="999+999")) |