282. Expression Add Operators

• 282. Expression Add Operators
  • Description
  • Intuition
  • Pitfall
  • Solution
  • Analysis
  • Reference

Description

Here

Intuition

这题我觉得最容易的方法是从basic calculator的套路入手

Pitfall

此题坑很多

1. 如果string是"05"或者"005", parse完都是5，所以表现到表达式上会变成5
2. 如果是第一次进入，我们只需要dfs加法的情况
   1. 因为-, *不能作为unary operator。所以当curPath.equals("")时，我们只用加法，不然-和*会相当于加入了dummy head.

Solution

  public List<String> addOperators(String num, int target) {
    final List<String> result = new ArrayList<>();
    dfs(result, target, num, "", 0, 0, 1);
    return result;
  }

  private static int deep = 0;

  private void dfs(final List<String> result, final int target, final String num, final String curPath,
                   final int start, final long curVal, final long curMul) {
//    ++deep;
    //    System.out.println(result + " target = " + target + " num = " + num + " curPath = " + curPath + " start = " + start + " curVal = " + curVal + " curMul = " + curMul);
//    System.out.println(indent() + result + " curPath = \"" + curPath + "\" start = " + start + " curVal = " + curVal +
//        " curMul = " + curMul);
    if (start == num.length()) {
      if (curVal + curMul == target) {
        result.add(curPath);
      }
//      --deep;
      return;
    } // end if start == num.length()

    // i is an inclusive end
    for (int i = start; i < num.length(); i++) {
      // TODO:Pitfall 1: Leading Zero. It is possible to have "05" -> 5, "005"
      if (i != start && num.charAt(start) == '0') {
        break;
      }
      final long curNum = Long.valueOf(num.substring(start, i + 1));
//      System.out.println(curVal + (curPath.length() == 0 ? 0 : curMul));
      // curVal + (curPath.length() == 0 ? 0 : curMul) 如果不打括号，先运算左边的加法
//      System.out.println(indent() + "Deep = " + (deep) + " calling add when i = " + i);
      dfs(result, target, num, curPath.length() == 0 ? "" + curNum : (curPath + "+" + curNum), i + 1,
          curVal + (curPath.length() == 0 ? 0 : curMul), curNum);
      if (curPath.length() != 0) { // TODO: Pitfall 2
//        System.out.println(indent() + "Deep = " + (deep) + " calling sub when i = " + i);
        dfs(result, target, num, curPath + "-" + curNum, i + 1,
            curVal + curMul, -curNum);
      }
      if (curPath.length() != 0) { // TODO: Pitfall 2
//        System.out.println(indent() + "Deep = " + (deep) + " calling multiple when i = " + i);
        dfs(result, target, num, curPath + "*" + curNum, i + 1,
            curVal, curMul * curNum);
      }
    }
//    --deep;
  }

Analysis

If we change the String + to a StringBuilder:

If we consider a string whose length is n, we have n - 1 void to insert "", +, - and *, so it can be easily concluded as 4^(N - 1)

If we consider from recursion,

#      Insert [0, 1], Insert [1, 2]  Insert [2, 3]
T(n)
= 3 * ( T(n - 1) + T(n - 2) + T(n - 3) + ... + T(1) )
= 3 * (3 * T(n - 2) + 3 * T(n - 3) + ... + 3 * T(1))
    + 3 * T(n - 2)
    + ...
    + 3 * T(1)
# 整理多项式
= 3 * 4 * ( T(n - 2) + T(n - 3) + ... + T(1) )
= ...
= 3 * 4 * 4 * ... * 4 * T(1)
= 3 * 4^(N - 2) * N
≈ 4 ^ (N - 2) * N

Time Complexity: O(4^(N - 1)) Space Complexity: O(3^N)

Reference