Expression Add Operators LeetCode Solution | Easy Approach

Expression Add Operators Given a string num that contains only digits and an integer target, return all possibilities to insert the binary operators '+', '-', and/or '*' between the digits of num so that the resultant expression evaluates to the target value.

Note that operands in the returned expressions should not contain leading zeros.

Example 1:

Input: num = "123", target = 6
Output: ["1*2*3","1+2+3"]
Explanation: Both "1*2*3" and "1+2+3" evaluate to 6.

Example 2:

Input: num = "232", target = 8
Output: ["2*3+2","2+3*2"]
Explanation: Both "2*3+2" and "2+3*2" evaluate to 8.

Example 3:

Input: num = "3456237490", target = 9191
Output: []
Explanation: There are no expressions that can be created from "3456237490" to evaluate to 9191.

Constraints:

• 1 <= num.length <= 10
• num consists of only digits.

Expression Add Operators Solutions

✅Time: O(n)
✅Space: O(n)

C++

class Solution {
 public:
  vector<string> addOperators(string num, int target) {
    vector<string> ans;
    dfs(num, target, 0, 0, 0, {}, ans);
    return ans;
  }

 private:
  string join(const vector<string>& path) {
    string joined;
    for (const string& s : path)
      joined += s;
    return joined;
  }

  // start index, prev value, current evaluated value
  void dfs(const string& num, int target, int start, long prev, long eval,
           vector<string>&& path, vector<string>& ans) {
    if (start == num.length()) {
      if (eval == target)
        ans.push_back(join(path));
      return;
    }

    for (int i = start; i < num.length(); ++i) {
      if (i > start && num[start] == '0')
        return;
      const string& s = num.substr(start, i - start + 1);
      const long curr = stol(s);
      if (start == 0) {
        path.push_back(s);
        dfs(num, target, i + 1, curr, curr, move(path), ans);
        path.pop_back();
      } else {
        for (const string& op : {"+", "-", "*"}) {
          path.push_back(op + s);
          if (op == "+")
            dfs(num, target, i + 1, curr, eval + curr, move(path), ans);
          else if (op == "-")
            dfs(num, target, i + 1, -curr, eval - curr, move(path), ans);
          else
            dfs(num, target, i + 1, prev * curr, eval - prev + prev * curr,
                move(path), ans);
          path.pop_back();
        }
      }
    }
  }
};

Java

 
class Solution {
  public List<String> addOperators(String num, int target) {
    List<String> ans = new ArrayList<>();
    dfs(num, target, 0, 0, 0, new StringBuilder(), ans);
    return ans;
  }

  private void dfs(String num, int target, int s, long prev, long eval, StringBuilder sb,
                   List<String> ans) {
    if (s == num.length()) {
      if (eval == target)
        ans.add(sb.toString());
      return;
    }

    for (int i = s; i < num.length(); ++i) {
      if (i > s && num.charAt(s) == '0')
        return;
      final long curr = Long.parseLong(num.substring(s, i + 1));
      final int length = sb.length();
      if (s == 0) { // first num
        dfs(num, target, i + 1, curr, curr, sb.append(curr), ans);
        sb.setLength(length);
      } else {
        dfs(num, target, i + 1, curr, eval + curr, sb.append("+").append(curr), ans);
        sb.setLength(length);
        dfs(num, target, i + 1, -curr, eval - curr, sb.append("-").append(curr), ans);
        sb.setLength(length);
        dfs(num, target, i + 1, prev * curr, eval - prev + prev * curr, sb.append("*").append(curr),
            ans);
        sb.setLength(length);
      }
    }
  }
}

Python

 class Solution:
  def addOperators(self, num: str, target: int) -> List[str]:
    ans = []

    # start index, prev value, current evaluated value
    def dfs(start: int, prev: int, eval: int, path: List[str]) -> None:
      if start == len(num):
        if eval == target:
          ans.append(''.join(path))
        return

      for i in range(start, len(num)):
        if i > start and num[start] == '0':
          return
        s = num[start:i + 1]
        curr = int(s)
        if start == 0:
          path.append(s)
          dfs(i + 1, curr, curr, path)
          path.pop()
        else:
          for op in ['+', '-', '*']:
            path.append(op + s)
            if op == '+':
              dfs(i + 1, curr, eval + curr, path)
            elif op == '-':
              dfs(i + 1, -curr, eval - curr, path)
            else:
              dfs(i + 1, prev * curr, eval - prev + prev * curr, path)
            path.pop()

    dfs(0, 0, 0, [])
    return ans

Watch Tutorial

Checkout more Solutions here