282. Expression Add Operators LeetCode Solution

In this guide, you will get 282. Expression Add Operators LeetCode Solution with the best time and space complexity. The solution to Expression Add Operators problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Expression Add Operators solution in C++
4. Expression Add Operators solution in Java
5. Expression Add Operators solution in Python
6. Additional Resources

Problem Statement of 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.
-231 <= target <= 231 – 1

Complexity Analysis

• Time Complexity: O(n4^{n – 1})
• Space Complexity: O(n^2)

282. Expression Add Operators LeetCode Solution in 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;
  }

  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, std::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, std::move(path), ans);
          else if (op == "-")
            dfs(num, target, i + 1, -curr, eval - curr, std::move(path), ans);
          else
            dfs(num, target, i + 1, prev * curr, eval - prev + prev * curr,
                std::move(path), ans);
          path.pop_back();
        }
      }
    }
  }
};
/* code provided by PROGIEZ */

282. Expression Add Operators LeetCode Solution in 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) { // the first number
        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);
      }
    }
  }
}
// code provided by PROGIEZ

282. Expression Add Operators LeetCode Solution in Python

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

    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
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.