Question

282. Expression Add Operators

中文文档

Description

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

Solutions

Solution 1

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

    def dfs(u, prev, curr, path):
      if u == len(num):
        if curr == target:
          ans.append(path)
        return
      for i in range(u, len(num)):
        if i != u and num[u] == '0':
          break
        next = int(num[u : i + 1])
        if u == 0:
          dfs(i + 1, next, next, path + str(next))
        else:
          dfs(i + 1, next, curr + next, path + "+" + str(next))
          dfs(i + 1, -next, curr - next, path + "-" + str(next))
          dfs(
            i + 1,
            prev * next,
            curr - prev + prev * next,
            path + "*" + str(next),
          )

    dfs(0, 0, 0, "")
    return ans

class Solution {
  private List<String> ans;
  private String num;
  private int target;

  public List<String> addOperators(String num, int target) {
    ans = new ArrayList<>();
    this.num = num;
    this.target = target;
    dfs(0, 0, 0, "");
    return ans;
  }

  private void dfs(int u, long prev, long curr, String path) {
    if (u == num.length()) {
      if (curr == target) ans.add(path);
      return;
    }
    for (int i = u; i < num.length(); i++) {
      if (i != u && num.charAt(u) == '0') {
        break;
      }
      long next = Long.parseLong(num.substring(u, i + 1));
      if (u == 0) {
        dfs(i + 1, next, next, path + next);
      } else {
        dfs(i + 1, next, curr + next, path + "+" + next);
        dfs(i + 1, -next, curr - next, path + "-" + next);
        dfs(i + 1, prev * next, curr - prev + prev * next, path + "*" + next);
      }
    }
  }
}

using System;
using System.Collections.Generic;

public class Expression
{
  public long Value;

  public override string ToString()
  {
    return Value.ToString();
  }
}

public class BinaryExpression : Expression
{
  public char Operator;

  public Expression LeftChild;
  public Expression RightChild;

  public override string ToString()
  {
    return string.Format("{0}{1}{2}", LeftChild, Operator, RightChild);
  }
}

public class Solution {
  public IList<string> AddOperators(string num, int target) {
    var results = new List<string>();
    if (string.IsNullOrEmpty(num)) return results;
    this.num = num;
    this.results = new List<Expression>[num.Length, num.Length, 3];
    foreach (var ex in Search(0, num.Length - 1, 0))
    {
      if (ex.Value == target)
      {
        results.Add(ex.ToString());
      }
    }
    return results;
  }

  private string num;
  private List<Expression>[,,] results;

  private List<Expression> Search(int left, int right, int level)
  {
    if (results[left, right, level] != null)
    {
      return results[left, right, level];
    }
    var result = new List<Expression>();
    if (level < 2)
    {
      for (var i = left + 1; i <= right; ++i)
      {
        List<Expression> leftResult, rightResult;
        leftResult = Search(left, i - 1, level);
        rightResult = Search(i, right, level + 1);
        foreach (var l in leftResult)
        {
          foreach (var r in rightResult)
          {
            var newObjects = new List<Tuple<char, long>>();
            if (level == 0)
            {
              newObjects.Add(Tuple.Create('+', l.Value + r.Value));
              newObjects.Add(Tuple.Create('-', l.Value - r.Value));
            }
            else
            {
              newObjects.Add(Tuple.Create('*', l.Value * r.Value));
            }
            foreach (var newObject in newObjects)
            {
              result.Add(new BinaryExpression
              {
                Value = newObject.Item2,
                Operator = newObject.Item1,
                LeftChild = l,
                RightChild = r
              });
            }
          }
        }
      }
    }
    else
    {
      if (left == right || num[left] != '0')
      {
        long x = 0;
        for (var i = left; i <= right; ++i)
        {
          x = x * 10 + num[i] - '0';
        }
        result.Add(new Expression
        {
          Value = x
        });
      }
    }
    if (level < 2)
    {
      result.AddRange(Search(left, right, level + 1));
    }
    return results[left, right, level] = result;
  }
}