diff options
author | Jack Sangdahl <[email protected]> | 2024-09-18 20:41:17 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-09-18 20:41:17 -0600 |
commit | 0e3a73d4a297707a2eba42ac8b1f4a04d63f1135 (patch) | |
tree | 730603028f1c54d8e58d3757798562befa07d370 /diff_add_parentheses.c | |
parent | 9b69e5b82a481b7131b55ece9d777318f43474b9 (diff) | |
download | leetcode-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.c | 122 |
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); } |