题目主要信息

1、给出一个数字串 2、在数字串中增加+、-、*使得形成表达式运算结果等于target

方法一:暴力解法

具体方法

在每个位置尝试加入' '、'+'、'-'、'*'，并计算结果，然后对所有情况进行计算，看是否满足条件

Java代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num string字符串 
     * @param target int整型 
     * @return string字符串一维数组
     */
    private int target;// 目标值
	private List<String> ans;// 答案
	private char[] nums;// num中间加空格
	private int len;// nums数组长度

	public String[] addOpt(String num, int target) {
		ans = new ArrayList<>();
		if (num.length() == 1) {
			if (target == Integer.valueOf(num)) {
				ans.add(num);
			}
			return ans.toArray(new String[ans.size()]);
		}
		this.target = target;// 设置目标
		this.blankNum(num);// num中间塞空格, 填满char[] nums
		f(1);// 决定第i个空格加什么东西
		return ans.toArray(new String[ans.size()]);
	}

	private void f(int i) {
		if (i == len - 1) {
			checkAnswer();// 判断char[] nums是否是有效的串, 更新答案
			return;
		}
		nums[i] = ' ';// 第i位不放符号
		f(i + 2);
		nums[i] = '-';// 第i位是 -
		f(i + 2);
		nums[i] = '+';// 第i位是 +
		f(i + 2);
		nums[i] = '*';// 第i位是 *-
		f(i + 2);
	}

	private void checkAnswer() {
		Stack<String> s = new Stack<>();
		StringBuffer cur = new StringBuffer();
		StringBuffer str = new StringBuffer();
		for (int i = 0; i < len; i++) {
			char c = nums[i];
			if (c == ' ')
				continue;
			str.append(c);
			if (c >= '0' && c <= '9') {
				if (cur.length() == 1 && cur.charAt(0) == '0')
					return;// 连着0的数字是错的, 01
				cur.append(c);
				continue;
			}
			if (c == '+' || c == '-' || c == '*') {
				if (!s.isEmpty() && s.peek().equals("*")) {
					s.pop();
					long num = Long.valueOf(s.pop());
					num *= Long.valueOf(cur.toString());
					if (num > Integer.MAX_VALUE) {
						return;// 数值超过int的是错的
					}
					s.add(String.valueOf(num));
				} else {
					long l = Long.valueOf(cur.toString());
					if (l > Integer.MAX_VALUE) {
						return;// 数值超过int的是错的
					}
					s.add(String.valueOf(l));
				}
				s.add(String.valueOf(c));
				cur.setLength(0);
			}
		}
		s.pop();// 结束位'+'
		int ans = 0;
		int last = 0;
		while (!s.isEmpty()) {
			String c = s.pop();
			if (c.equals("+")) {
				ans += last;
			} else if (c.equals("-")) {
				ans -= last;
			} else {
				last = Integer.valueOf(c);
			}
		}
		ans += last;
		if (ans == target) {
			this.ans.add(str.substring(0, str.length() - 1));
		}
	}

	private void blankNum(String num) {
		len = (num.length() << 1);
		nums = new char[len];
		int p = 0;
		for (int i = 0; i < num.length(); i++) {
			nums[p] = num.charAt(i);
			p += 2;
		}
		nums[len - 1] = '+';// 结束位'+'
	}
}

复杂度分析

时间复杂度： $O (n * 4^{n})$ ，总共 $O (4^{n})$ 种可能，每一种可能的计算时间复杂度为 $O (n)$
空间复杂度： $O (n)$ ，空间复杂度取决于递归的深度

方法二：dfs

具体方法

设字符串num 的长度为 n，为构建表达式，我们可以往 num中间的 n−1 个空隙添加+号、-号或*号，或者不添加符号。

我们可以用「回溯法」来模拟这个过程。从左向右构建表达式，并实时计算表达式的结果。由于乘法运算优先级高于加法和减法运算，我们还需要保存最后一个连乘串（如 234）的运算结果。

定义递归函数 backtrack(expr,i,res,mul)，其中：

expr为当前构建出的表达式；
i表示当前的枚举到了 num的第 i 个数字；
res为当前表达式的计算结果；
mul 为表达式最后一个连乘串的计算结果。

该递归函数分为两种情况：

如果 i=n，说明表达式已经构造完成，若此时有 res=target，则找到了一个可行解，我们将 expr 放入答案数组中，递归结束；
如果 i<n，需要枚举当前表达式末尾要添加的符号（+号、-号或 *号），以及该符号之后需要截取多少位数字。设该符号之后的数字为 val，按符号分类讨论：
- 若添加 + 号，则 res 增加 val，且 val单独组成表达式最后一个连乘串；
- 若添加 -\号，则 res减少 val，且 −val 单独组成表达式最后一个连乘串；
- 若添加 *号，由于乘法运算优先级高于加法和减法运算，我们需要对 res撤销之前 mul 的计算结果，并添加新的连乘结果 mul∗val，也就是将 res 减少 mul并增加 mul∗val。

Java代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num string字符串 
     * @param target int整型 
     * @return string字符串一维数组
     */
    int n;
    String num;
    int target;
    List<String> ans;
    public String[] addOpt (String num, int target) {
        // write code here
        this.n = num.length();
        this.num = num;
        this.target = target;
        this.ans = new ArrayList<String>();
        StringBuffer expr = new StringBuffer();
        backtrack(expr, 0, 0, 0);
        return ans.toArray(new String[ans.size()]);
    }
    public void backtrack(StringBuffer expr, int i, long res, long mul) {
        if (i == n) {
            if (res == target) {
                ans.add(expr.toString());
            }
            return;
        }
        int signIndex = expr.length();
        if (i > 0) {
            expr.append(0); // 占位，下面填充符号
        }
        long val = 0;
        // 枚举截取的数字长度（取多少位），注意数字可以是单个 0 但不能有前导零
        for (int j = i; j < n && (j == i || num.charAt(i) != '0'); ++j) {
            val = val * 10 + num.charAt(j) - '0';
            expr.append(num.charAt(j));
            if (i == 0) { // 表达式开头不能添加符号
                backtrack(expr, j + 1, val, val);
            } else { // 枚举符号
                expr.setCharAt(signIndex, '+');
                backtrack(expr, j + 1, res + val, val);
                expr.setCharAt(signIndex, '-');
                backtrack(expr, j + 1, res - val, -val);
                expr.setCharAt(signIndex, '*');
                backtrack(expr, j + 1, res - mul + mul * val, mul * val);
            }
        }
        expr.setLength(signIndex);
    }
}

复杂度分析

时间复杂度： $O (4^{n})$ ，，其中n是字符串 num的长度。由于在数字之间可以选择不添加符号、添加+号、-号或*号，一共有 4种选择，因此时间复杂度为 $O (4^{n})$
空间复杂度： $O (n)$ ，空间复杂度取决于递归时的栈空间。

题解 | #给表达式添加运算符#

题目主要信息

方法一:暴力解法

具体方法

Java代码

复杂度分析

方法二：dfs

具体方法

Java代码

复杂度分析