LintCode 653 / LeetCode 282 Expression Add Operators

思路

枚举型dfs。暴力枚举搜索，通过枚举所有的可能数字组合形式来看是否符合要求。每次枚举当前数字和其符号，对于+或-直接在结果val上进行加减操作即可，但是对于就需要使用一个lastFactor变量存储上一个连乘的结果，当前value=value-lastFactor+curlastFactor(原理是首先将上一个+/-的数也就是连乘的数lastFactor还原回去，然后再将其与cur相乘加到value上)，并将其更新为lastFactor*cur。

需要注意：
（1）对于第一个数字，只能默认为其符号为+，因此其递归参数path有所不同；对于其他位置开始的数字，分别枚举+/-/*的情况。
（2）需要去掉带有前导0的所有数字，也就是说0只能使用1次，一旦0与后面的任何一个数字结合为一个带有前导0的新字符串，就应该舍弃，因此在递归搜索之后（因为可以使用1次0，i每次递增1）加入对于cur的判断。
（3）由于中间结果可能溢出，所以cur和val都使用long类型。

代码

LintCode 653

public class Solution {
    /*** @param num: a string contains only digits 0-9* @param target: An integer* @return: return all possibilities*/private void dfs(String num, int target, int start, String path, long val, long lastF, List<String> res) {
    if(start == num.length()) {
    if(val == target) {
    res.add(path);}return;}for(int i = start; i < num.length(); i++) {
    long cur = Long.parseLong(num.substring(start, i + 1));if(start == 0) {
    dfs(num, target, i + 1, "" + cur, val + cur, cur, res);} else {
    dfs(num, target, i + 1, path + "*" + cur, val - lastF + lastF * cur, lastF * cur, res);dfs(num, target, i + 1, path + "+" + cur, val + cur, cur, res);dfs(num, target, i + 1, path + "-" + cur, val - cur, -cur, res);}// 对于任何带有前导0的数字组合即cur，都要被淘汰// i.e.任何的0都能且仅能使用1次，一旦与后面的任何数字组合都要淘汰if(cur == 0) {
    break;}}}public List<String> addOperators(String num, int target) {
    // write your code hereList<String> res = new ArrayList<>();if(num == null || num.length() == 0) {
    return res;}dfs(num, target, 0, "", 0, 0, res);return res;}
}

复杂度

时间复杂度$O(n?4^n)$: 见笔记或LC上的讲解
空间复杂度$O(n)$：不考虑res的大小，因为我们无法控制
We don’t consider the space occupied by the answers array since that is a part of the question’s requirement and we can’t reduce that in any way