aboutsummaryrefslogtreecommitdiff
path: root/diff_add_parentheses.c
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-09-18 20:41:17 -0600
committerJack Sangdahl <[email protected]>2024-09-18 20:41:17 -0600
commit0e3a73d4a297707a2eba42ac8b1f4a04d63f1135 (patch)
tree730603028f1c54d8e58d3757798562befa07d370 /diff_add_parentheses.c
parent9b69e5b82a481b7131b55ece9d777318f43474b9 (diff)
downloadleetcode-0e3a73d4a297707a2eba42ac8b1f4a04d63f1135.tar.gz
leetcode-0e3a73d4a297707a2eba42ac8b1f4a04d63f1135.zip
241. different ways to add parentheses
Diffstat (limited to 'diff_add_parentheses.c')
-rw-r--r--diff_add_parentheses.c122
1 files changed, 61 insertions, 61 deletions
diff --git a/diff_add_parentheses.c b/diff_add_parentheses.c
index d9ecf4e..d9329df 100644
--- a/diff_add_parentheses.c
+++ b/diff_add_parentheses.c
@@ -1,82 +1,82 @@
// 241. Different Ways to Add Parentheses
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
+#include "leetcode.h"
/*
* given a string 'expression' of numbers and operators, return all possible
* results from computing all the different possible ways to group numbers and
* operators. you may return the answer in any order. the test cases are
* generated such that the output values fit in a 32-bit integer and the number
- * of different results is <10^4
+ * of different results does not exceed 10^4
*/
-#define CAL(a, b, op) ('+' == op ? a + b : '-' == op ? a - b : a * b)
-
-void token_size(char *s, char **op, int **num, int *return_size) {
- int i, s_len = (int)strlen(s), len = 0;
- int *res = malloc(sizeof(int) * ((s_len + 1) >> 1));
- char *ops = malloc(s_len >> 1);
- res[0] = 0;
- for (int i = 0; i < s_len; ++i) {
- if ('0' > s[i] || s[i] > '9') {
- ops[len++] = s[i];
- res[len] = 0;
- } else
- res[len] = res[len] * 10 + s[i] - '0';
+int compute(int a, int b, char op) {
+ switch (op) {
+ case '+':
+ return a + b;
+ case '-':
+ return a - b;
+ case '*':
+ return a * b;
+ default:
+ return 0;
}
- len++;
- *return_size = len;
- *num = res;
- *op = ops;
}
-int *helper(int *return_size, int *nums, int len, char *op) {
- int i, j, k, cnt = 0, cap = 10, *set = malloc(sizeof(int) * cap);
- int *ss1 = NULL, *ss2 = NULL, sl1 = 0, sl2 = 0;
- if (2 >= len) {
- set[cnt++] = 1 == len ? nums[0] : CAL(nums[0], nums[1], op[0]);
- *return_size = cnt;
- return set;
- }
- for (i = 1; i <= len - 1; ++i) {
- ss1 = helper(&sl1, nums, i, op);
- ss2 = helper(&sl2, nums + i, len - i, op + i);
- if (cnt + sl1 * sl2 >= cap) {
- cap += (sl1 * sl2) << 1;
- set = realloc(set, sizeof(int) * cap);
- }
- for (j = 0; j < sl1; ++j)
- for (k = 0; k < sl2; ++k)
- set[cnt++] = CAL(ss1[j], ss2[k], op[i - 1]);
- free(ss1);
- free(ss2);
- }
- *return_size = cnt;
- return set;
+bool is_num(char *expression) {
+ for (int i = 0; i < strlen(expression); i++)
+ if (!isdigit(expression[i]))
+ return false;
+ return true;
}
-int *diffWaysToCompute(char *expression, int *return_size) {
- int *nums, *ans, len;
- char *op;
- if (!expression) {
- *return_size = 0;
- return NULL;
+int *grow_array(int *arr, int curr_size, int new_size) {
+ return (int *)realloc(arr, new_size * sizeof(int));
+}
+
+int *diffWaysToCompute(char *expression, int *returnSize) {
+ int capacity = 10;
+ int *ans = (int *)malloc(capacity * sizeof(int));
+ *returnSize = 0;
+ if (is_num(expression)) {
+ ans[0] = atoi(expression);
+ *returnSize = 1;
+ return ans;
+ }
+ for (int i = 0; i < strlen(expression); i++) {
+ char e = expression[i];
+ if (e == '+' || e == '-' || e == '*') {
+ char left[100], right[100];
+ strncpy(left, expression, i);
+ left[i] = '\0';
+ strcpy(right, expression + i + 1);
+ int left_size, right_size;
+ int *left_ans = diffWaysToCompute(left, &left_size);
+ int *right_ans = diffWaysToCompute(right, &right_size);
+ for (int l = 0; l < left_size; l++)
+ for (int r = 0; r < right_size; r++) {
+ if (*returnSize >= capacity) {
+ capacity *= 2;
+ ans = grow_array(ans, capacity / 2, capacity);
+ }
+ ans[*returnSize] = compute(left_ans[l], right_ans[r], e);
+ (*returnSize)++;
+ }
+ free(left_ans), free(right_ans);
+ }
}
- token_size(expression, &op, &nums, &len);
- ans = helper(return_size, nums, len, op);
- free(op);
- free(nums);
return ans;
}
int main() {
- char e1[] = {"2 - 1 - 1"}, e2[] = {"2 * 3 - 4 * 5"};
- int *dwtc1 = diffWaysToCompute(e1, NULL);
- int *dwtc2 = diffWaysToCompute(e2, NULL);
- for (int i = 0; i < 2; i++)
- printf("%d ", dwtc1[i]); // expect: 0,2
+ char *e1 = "2-1-1", *e2 = "2*3-4*5";
+ int rs1, rs2;
+ int *dwtc1 = diffWaysToCompute(e1, &rs1),
+ *dwtc2 = diffWaysToCompute(e2, &rs2);
+ for (int i = 0; i < rs1; i++)
+ printf("%d ", dwtc1[i]); // expect: 0 2
+ printf("\n");
+ for (int i = 0; i < rs2; i++)
+ printf("%d ", dwtc2[i]); // expect: -34 -14 -10 -10 10
printf("\n");
- for (int i = 0; i < 5; i++)
- printf("%d ", dwtc2[i]); // expect: -34,-14,-10,-10,10
+ free(dwtc1), free(dwtc2);
}