Expression Add Operators Promblem

This problem is from the LeetCode#282

Problem

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

"123", 6 -> ["1+2+3", "1*2*3"] 
"232", 8 -> ["2*3+2", "2+3*2"]
"105", 5 -> ["1*0+5","10-5"]
"00", 0 -> ["0+0", "0-0", "0*0"]
"3456237490", 9191 -> []

 

Rough Idea

The total number that we need calculate (length of the string) is not given. We need to traverse all the possibles and find out all equatioins that meet the target number. We can solve the problem use both Breadth-First Search (BFS) and Depth-First Search. Only we meet two conditions which are we travelled all number and the vaule is equal to target number at the same time, we can add the equation to the result list.

Implementation method

I’m going to use a helper method to traverse it. this method will take the a arraylist to store string type result, the number set and the target number that have given us, a string to hold the current path (like 1+2 or 2+3*4-1), a integer to mark the current positon, and two long number to store the current calculation solution and the last calculation solution. It put the position to the for loop to calculate the current number with all three operation (+,-,×). If it satisfy the condition, we add the result to the list, or we can jump into the helper method again to calculate the next number.

Solution Code [Java]

import java.util.*;

class Solution {
    public List<String> addOperators(String num, int target) {
        List<String> result = new ArrayList<>();
        if(num == null || num.length() == 0){
            return result;
        }
        calculate(result, num, target, "",0,0,0);
        return result;
    }

    private void calculate(List<String> list, String num, int target, String path, int pos, long val, long pre) {
        if(pos == num.length() && val == target) {
            list.add(path);
        }

        for(int i = pos; i < num.length(); i++) {
            if(i != pos && num.charAt(pos) == '0') {
                break;
            }
            long cur = Long.parseLong(num.substring(pos, i + 1));
            if(pos == 0) {
                calculate(list, num, target, path + cur, i + 1, cur, cur);
            } else {
                calculate(list, num, target, path + "+" + cur, i + 1, val + cur, cur);
                calculate(list, num, target, path + "-" + cur, i + 1, val - cur, -cur);
                calculate(list, num, target,  path + "*" + cur, i + 1, val - pre + pre * cur, pre * cur);
            }
        }
    }
}

There’s a interesting thing. How to calculate the result when computer need put a multiplication operator? We can minus the first number that our program has added to the previous number. and plus the product that the current number times the last number we just minus. For example, the 1 + 2 * 3 will be the 7, but program will calculate 1 + 2 first, then times 3 when it goes into a deeper method. so, it should looks like 1 + 2 + [ (-2) + 2 * 3 ] .

Test Code [Java]

import java.util.*;

public class applicationTest {

    public static void main(String[] args) {
        Solution solution = new Solution();
        List<String> list = solution.addOperators("3456237490", 9191);
        for(String str : list) {
            System.out.println(str);
        }
    }
}