C recursive solution, 0 ms.


  • 0
    H
    #define CAL(a, b, op) ('+' == op ? a + b : '-' == op ? a - b : a * b)
    void tokenize(char* s, char** op, int** num, int* returnSize) {
        int i, slen = (int) strlen(s), len = 0, *ret = malloc(sizeof(int) * ((slen + 1) >> 1));
        char* ops = malloc(slen >> 1);
        ret[0] = 0;
        for (i = 0; i < slen; ++i) {
            if ('0' > s[i] || s[i] > '9') {
                ops[len++] = s[i];
                ret[len] = 0;
            } else {
                ret[len] = ret[len] * 10 + s[i] - '0';
            }
        }
        len++;
        *returnSize = len;
        *num = ret;
        *op = ops;
    }
    int* helper(int* returnSize, int* nums, int len, char* op) {
        int i, j, k, count = 0, cap = 10, *set = malloc(sizeof(int) * cap);
        int *subset1 = NULL, *subset2 = NULL, sublen1 = 0, sublen2 = 0;
        if (2 >= len) {
            set[count++] = 1 == len ? nums[0] : CAL(nums[0], nums[1], op[0]);
            *returnSize = count;
            return set;
        }
        for (i = 1; i <= len - 1; ++i) {
            subset1 = helper(&sublen1, nums, i, op);
            subset2 = helper(&sublen2, nums + i, len - i, op + i);
            if (count + sublen1 * sublen2 >= cap) {
                cap += (sublen1 * sublen2) << 1;
                set = realloc(set, sizeof(int) * cap);
            }
            for (j = 0; j < sublen1; ++j) {
                for (k = 0; k < sublen2; ++k) {
                    set[count++] = CAL(subset1[j], subset2[k], op[i - 1]);
                }
            }
            free(subset1);
            free(subset2);
        }
        *returnSize = count;
        return set;
    }
    /**
     * Return an array of size *returnSize.
     * Note: The returned array must be malloced, assume caller calls free().
     */
    int* diffWaysToCompute(char* input, int* returnSize) {
        int *nums, len, *result;
        char *op;
        if (!input) {
            *returnSize = 0;
            return NULL;
        }
        tokenize(input, &op, &nums, &len);
        result = helper(returnSize, nums, len, op);
        free(op);
        free(nums);
        return result;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.