NUHMAN.com

🔍 Problem Statement

Given a string expression that contains digits and operators (+, -, *), return all possible results from computing all the different possible ways to group numbers and operators.

You may assume that the given expression is valid. For example:

go

Input: expression = "2-1-1"
Output: [0, 2]
Explanation:
  ((2-1)-1) = 0
  (2-(1-1)) = 2

🧠 Approach

This problem can be solved using recursion and divide and conquer. The idea is to recursively divide the expression into two parts and compute the result for each part. Then combine the results using the operators in between.

Here are the steps:

1. Base Case: If the expression contains only a number (i.e., no operators), return that number.
2. Recursive Case:

• For every operator in the expression, split the string into two parts — one to the left of the operator and the other to the right.
• Recursively calculate the result for the left and right parts.
• Combine the results using the operator and store the result.

The core of the solution is to treat the expression as a combination of smaller subproblems. This can be achieved using recursion to break down the problem, and then combining the results.

Steps:

1. Recursive function: Implement a helper function that can handle the string recursively.
2. Loop through the expression: For each operator (+, -, or *), split the string into two parts — one left of the operator and the other right of the operator.
3. Combine the results: Recursively calculate results for each side and then combine them using the operator.
4. Return results: After processing all operators, return all computed results.

✅ Go Implementation

go

package main

import (
	"fmt"
	"strconv"
)

// Helper function to compute all possible results by splitting the expression
func diffWaysToCompute(expression string) []int {
	// Base case: If the expression is just a number
	if isNumber(expression) {
		num, _ := strconv.Atoi(expression)
		return []int{num}
	}

	var result []int
	// Loop through the expression and split at each operator
	for i := 0; i < len(expression); i++ {
		// If we encounter an operator, split the expression into two parts
		if expression[i] == '+' || expression[i] == '-' || expression[i] == '*' {
			// Recursively compute the results of both parts
			left := diffWaysToCompute(expression[:i])
			right := diffWaysToCompute(expression[i+1:])

			// Combine the results of left and right parts
			for _, l := range left {
				for _, r := range right {
					switch expression[i] {
					case '+':
						result = append(result, l+r)
					case '-':
						result = append(result, l-r)
					case '*':
						result = append(result, l*r)
					}
				}
			}
		}
	}

	return result
}

// Helper function to check if the string is just a number
func isNumber(s string) bool {
	for i := 0; i < len(s); i++ {
		if s[i] < '0' || s[i] > '9' {
			return false
		}
	}
	return true
}

// Helper function to print the result
func printResult(result []int) {
	fmt.Println(result)
}

// Test the diffWaysToCompute function
func main() {
	// Example 1: "2-1-1"
	expression1 := "2-1-1"
	result1 := diffWaysToCompute(expression1)
	printResult(result1) // Output: [0, 2]

	// Example 2: "2*3-4*5"
	expression2 := "2*3-4*5"
	result2 := diffWaysToCompute(expression2)
	printResult(result2) // Output: [-34, -14, -10, -10, 10]
}

🧑‍💻 Explanation of the Code

1. diffWaysToCompute function:

• Base Case: If the expression is a simple number (no operators), we return the number itself.
• Recursive Case: For each operator in the expression (+, -, or *), we:
• Split the expression into two parts: left of the operator and right of the operator.
• Recursively compute the results for the left and right parts.
• Combine the results by applying the operator (+, -, or *).

1. isNumber function:

• This function checks if the string s is a valid number (contains only digits). It is used to handle the base case where the expression is just a number.

1. printResult function:

• A helper function to print the result as a list of integers.

1. main function:

• It runs the diffWaysToCompute function on two examples and prints the results.

📦 Example Usage

go

func main() {
	// Example 1: "2-1-1"
	expression1 := "2-1-1"
	result1 := diffWaysToCompute(expression1)
	printResult(result1) // Output: [0, 2]

	// Example 2: "2*3-4*5"
	expression2 := "2*3-4*5"
	result2 := diffWaysToCompute(expression2)
	printResult(result2) // Output: [-34, -14, -10, -10, 10]
}

Example Output:

css

[0, 2]
[-34, -14, -10, -10, 10]

⏱️ Time & Space Complexity

• Time Complexity: The time complexity is O(2^n) where n is the length of the expression. This is because for each operator, we split the expression into two subproblems. The number of subproblems grows exponentially as the number of operators increases.
• Space Complexity: The space complexity is O(n) due to the recursion stack and the space used to store intermediate results.

This solution leverages recursion and divide-and-conquer principles to handle the problem effectively.