*Java* dfs method with explanations


  • 1
    E

    Idea:

    • divide the string into three pieces:
      & * #
      where
      & is the already constructed string that is independent of the remaining part, i.e., & and * are not connected with a multiplication

      • is the current value

      is the remaining string

      the remaining task is to work on the

      string such that its evaluation is exactly target - eval(&), and let's denote it as rem

    • there are three ways to connect * with #:

      add, subtract, multiply

    • if * and # are collected with add or subtract, we know that & is independent of *, so we only need

      eval(&) = rem - *

    • if * and # are collected with multiply, we know that & is dependent on *, so we use a prevNum to store the value of * for future use

    Code:

    public List<String> addOperators(String num, int target) {
        List<String> res = new LinkedList<>();
        backtrack(num.toCharArray(), res, "", 0, target, 0);
        return res;
    }
    
    private void backtrack(char[] nums, List<String> res, String str, int pos, long rem, long prevNum) {
        if(rem == prevNum && pos == nums.length) {
            res.add(str);
            return;
        }
        long val = 0;
        for(int i=pos; i<nums.length; i++) {
            val = val*10 + (nums[i]-'0');
            if(i>pos && nums[pos]=='0') break;
            if(pos==0) backtrack(nums, res, ""+val, i+1, rem, val);
            else {
                backtrack(nums, res, str+"+"+val, i+1, rem-prevNum, val);
                backtrack(nums, res, str+"-"+val, i+1, rem-prevNum, -val);
                backtrack(nums, res, str+"*"+val, i+1, rem, prevNum*val);
            }
        }
    }

  • 0
    S

    Why this is called DFS? Is this solution related to graphs somehow?


  • 0
    A

    Hi,

    I have a question of the long val value in the recursion, seems it is based on the assumption that String num will not exceed the Long's range.


  • 0
    A

    @sergey.emantayev

    you can draw the recursion tree, this algorithm will traverse that tree by DFS


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.