LeetCode //C - 241. Different Ways to Add Parentheses

241. Different Ways to Add Parentheses

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 does not exceed 1 0 4 10^4 104.
 

Example 1:

Example 2:

Constraints:

• 1 <= expression.length <= 20
• expression consists of digits and the operator ‘+’, ‘-’, and ‘*’.
• All the integer values in the input expression are in the range [0, 99].

From: LeetCode
Link: 241. Different Ways to Add Parentheses

---

Solution:

Ideas:

1. isSingleNumber Check: Added a function to check if the entire expression is a single number, ensuring proper handling of such cases.
2. Base Case Handling: Properly handle the base case by checking if the expression is a single number.
3. Correct Recursive Division: Ensure the expression is correctly divided and each part is processed recursively.
4. Memory Management: Ensured dynamic memory allocation for storing results and properly freeing allocated memory.

Code:

#define MAX_RESULTS 10000

// Helper function to determine if the input is a single number
int isSingleNumber(char* expression) {
    for (int i = 0; expression[i] != '\0'; i++) {
        if (!isdigit(expression[i])) {
            return 0;
        }
    }
    return 1;
}

int* diffWaysToCompute(char* expression, int* returnSize) {
    int* results = (int*)malloc(MAX_RESULTS * sizeof(int));
    *returnSize = 0;

    if (isSingleNumber(expression)) {
        int value = atoi(expression);
        results[0] = value;
        *returnSize = 1;
        return results;
    }
    
    for (int i = 0; expression[i] != '\0'; i++) {
        if (expression[i] == '+' || expression[i] == '-' || expression[i] == '*') {
            // Split the expression into two parts
            char left[i + 1];
            strncpy(left, expression, i);
            left[i] = '\0';
            char* right = expression + i + 1;
            
            // Recursively compute results for the left and right parts
            int leftSize, rightSize;
            int* leftResults = diffWaysToCompute(left, &leftSize);
            int* rightResults = diffWaysToCompute(right, &rightSize);
            
            // Combine the results from the left and right parts
            for (int j = 0; j < leftSize; j++) {
                for (int k = 0; k < rightSize; k++) {
                    if (expression[i] == '+') {
                        results[(*returnSize)++] = leftResults[j] + rightResults[k];
                    } else if (expression[i] == '-') {
                        results[(*returnSize)++] = leftResults[j] - rightResults[k];
                    } else if (expression[i] == '*') {
                        results[(*returnSize)++] = leftResults[j] * rightResults[k];
                    }
                }
            }
            
            free(leftResults);
            free(rightResults);
        }
    }
    
    return results;
}