282.给表达式添加运算符

链接：282.给表达式添加运算符
难度：Hard
标签：数学、字符串、回溯
简介：给定一个仅包含数字  0-9  的字符串 num 和一个目标值整数 target ，在 num 的数字之间添加 二元 运算符（不是一元）+、-  或  * ，返回所有能够得到目标值的表达式。

题解 1 - typescript

• 编辑时间：2021-10-16
• 执行用时：7944ms
• 内存消耗：103.7MB
• 编程语言：typescript
• 解法介绍：dfs。

function addOperators(num: string, target: number): string[] {
  const n = num.length;
  if (n === 1) {
    return +num === target ? [num] : [];
  }
  const ops = ['+', '-', '*', ''];
  const ans = new Set<string>();
  dfs();
  return Array.from(ans);
  function dfs(idx = 0, template = '') {
    if (idx === n) {
      if (eval(template) === target) ans.add(template);
      return;
    }
    const current = num[idx];
    template += current;
    if (idx === n - 1) {
      dfs(idx + 1, template);
      return;
    }
    for (const op of ops) {
      if (num[idx] === '0' && op === '') continue;
      dfs(idx + 1, template + op);
    }
    while (idx < n - 1 && current !== '0' && num[idx + 1] === '0') {
      template += '0';
      dfs(idx + 2, template);
      idx += 1;
    }
  }
}