Leetcode Expression Add Operators (Java)

Tags: ,

Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or *between the digits so they evaluate to the target value.

Examples:

Analysis:

This problem can be solved using DFS algorithm. For example, given the input “123456“, suppose we encounter the last digit “6”, at which we already have the result of solve(“12345“). Then there are three cases:

solve(“123456”) = solve(“12345”) + 6

solve(“123456”) = solve(“12345”) – 6

solve(“123456”) = cal( solve(“12345”) , 6, *), this have the following three cases:

  1. suppose solve(“12345”) = solve(“1234”) + 5,  so we have solve(“123456”) = solve(“1234“) + 5 * 6
  2. suppose solve(“12345”) = solve(“123”) + 4  * 5,  so we have solve(“123456”) = solve(“123“) + 4 * 5 * 6
  3. suppose solve(“12345”) = solve(“1234”)  –  5,  so we have solve(“123456”) = solve(“1234“) - 5 * 6. 

From the above three cases , we can see that in the step of solve(“123456“), we already have solve(“12345“), we also need to have the value of solve(“1234“), and 5 for case 1, 3; and solve(“123”) and 4*5 for case 2. 

In the above case 1, we define preSum = solve(“1234”) + 5, and preVal = 5, then we have solve(“1234”) = solve(“12345”) – 5 = preSum – preVal. 

In the above case 2, we define preSum = solve(“123”) + 4*5 ,and preVal = 4 * 5, then we have solve(“123”) = solve(“12345”) – 4*5 = preSum – preVal.

in the above case 3, we define preSum = solve(“1234”) – 5, and preVal = -5, then we have solve(“1234”) = solve(“12345”) – (-5) = preSum – preVal. 

So in the recursive process, we need to track the preSum, and preVal based on the operators. See the following Java implementation for details.

Java Solution: