282. Expression Add Operators.md

282. Expression Add Operators

Question

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.

Example 1:

Input: num = "123", target = 6
Output: ["1+2+3", "1*2*3"]

Example 2:

Input: num = "232", target = 8
Output: ["2*3+2", "2+3*2"]

Example 3:

Input: num = "105", target = 5
Output: ["1*0+5","10-5"]

Example 4:

Input: num = "00", target = 0
Output: ["0+0", "0-0", "0*0"]

Example 5:

Input: num = "3456237490", target = 9191
Output: []

Solution

1. Use dfs to solve this question.

class Solution {
    public List<String> addOperators(String num, int target) {
        List<String> result = new LinkedList<>();
        dfs(result, num, "", 0, 0, 0, target);
        return result;
    }
    private void dfs(List<String> result, String num, String path, int pos, long sum, long last, int target){
        int len = num.length();
        // If position meets the end and sum meets the target, we can add the value into the list.
        if(pos == len && sum == target) result.add(path);
        for(int i = pos; i < len; i++){
            if(i != pos && num.charAt(pos) == '0') break;
            long cur = Long.parseLong(num.substring(pos, i + 1));
            if(pos == 0){
                //Starts from begining, we just need to save the value.
                dfs(result, num, ""+cur, i + 1, cur, cur, target);
            }else{
                dfs(result, num, path + "+" + cur, i + 1, sum + cur, cur, target);
                // For next turn, current value is -cur, since we always use sum - last to get previous value.
                dfs(result, num, path + "-" + cur, i + 1, sum - cur, -cur, target);
                // multiplication is a little bit special, we take the last * cur as cur, and sum need to take the previous value terms as a term and we need to minus the previous term and use the previous term times current value and add to the sum.
                dfs(result, num, path + "*" + cur, i + 1, sum - last + last * cur, last * cur, target);
            }
        }
    }
}

Second time

• Method 1: dfs

  class Solution {
      public List<String> addOperators(String num, int target) {
          List<String> result = new ArrayList<>();
          dfs(result, num, "", 0, 0, 0, target);
          return result;
      }
      private void dfs(List<String> result, String num, String prefix, int index, long pre, long cur, int target){
          if(index == num.length() && cur == target){
              result.add(prefix);
          }
          for(int i = index; i < num.length(); i++){
              if(i != index && num.charAt(index) == '0') break;
              long temp = Long.parseLong(num.substring(index, i + 1));
              if(index == 0){
                  dfs(result, num, "" + temp, i + 1, temp, temp, target);
              }else{
                  dfs(result, num, prefix + "+" + temp, i + 1, temp, cur + temp, target);
                  dfs(result, num, prefix + "-" + temp, i + 1, -temp, cur - temp, target);
                  dfs(result, num, prefix + "*" + temp, i + 1, pre * temp, cur - pre + pre * temp, target);
              }
          }
      }
  }

Reference

1. 花花酱 LeetCode 282. Expression Add Operators