Problem: Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.
Example(Taken from leetcode):
Input: "2-1-1"
Output: [0, 2]
Explanation:
((2-1)-1) = 0
(2-(1-1)) = 2
Approach: We can solve this problem by parenthesizing all possible valid substring of the expression and then evaluating them, but as you can see it involves solving lots of subproblems which are already solved before or you can say solving lots of repeating subproblem which clearly tells us that we can use DP here.
We can have a HashMap whose key is substring and value is all possible results for that substring. Basically we will memorize the results of a substring and whenever we try to solve the same substring again, we just get the result from the HashMap.
For each character in the input string, we check if the current character is operator then we divide the input into two parts; one before operator and second after operator. Recursively solve each part and then combine the result in all possible ways.
Implementation in C#:
public static IList<int> DiffWaysToCompute(string input)
{
if (string.IsNullOrWhiteSpace(input))
{
return new List<int>();
}
Dictionary<string, List<int>> memory = new Dictionary<string, List<int>>();
return DiffWaysToCompute(input, ref memory);
}
private static List<int> DiffWaysToCompute(string input, ref Dictionary<string, List<int>> memory)
{
// Checking if the current string is already solved
if (memory.ContainsKey(input))
{
return memory[input];
}
List<int> result = new List<int>();
for (int i = 0; i < input.Length; ++i)
{
if (IsOperator(input[i]))
{
List<int> resultsBeforeOperator = DiffWaysToCompute(input.Substring(0, i), ref memory);
List<int> resultAfterOperator = DiffWaysToCompute(input.Substring(i + 1), ref memory);
foreach(int preNum in resultsBeforeOperator)
{
foreach(int postNum in resultAfterOperator)
{
switch(input[i])
{
case '+': result.Add(preNum + postNum);
break;
case '-': result.Add(preNum - postNum);
break;
case '*': result.Add(preNum * postNum);
break;
}
}
}
}
}
// The whole string was a number
if (result.Count == 0)
{
result.Add(int.Parse(input));
}
memory.Add(input, result);
return result;
}
private static bool IsOperator(char ch)
{
return ch == '+' || ch == '-' || ch == '*';
}
Complexity: O(2^n)
