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

题意整理

• 给定一个仅包含数字的字符串num和一个目标值target。
• 在num的数字之间添加"+","-"或"*",返回所有能够得到目标值的表达式。

方法一（位运算）

1.解题思路

可以分两步解决，第一步将运算符添加到字符串num，组成一个表达式，找到所有可能的表达式，第二步校验生成的表达式，计算表达式的值是否为target，如果是，则加入到结果中。

• 将运算符添加到num中的过程可以使用位运算，n个字符中总共有n-1个空可以插入运算符，每个空可以选择不插入、插入"+"、插入"-"、插入"*"。我们用00表示不插入、用01表示插入"+"、用10表示插入"-"、用11表示插入"*"。所以n-1个空对应$2^{2\ast n-2}2^\{2*n-2\}$个mask位。
• 遍历所有的mask位，添加对应的运算符，组成一个可能的表达式。
• 如果表达式没有前导0，并且值等于target，则加入到结果中。计算表达式的值，可以通过栈来做（将每一个带符号的数加入到栈中，最后将栈中所有的数相加即可）。

图解展示：

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num string字符串 
     * @param target int整型 
     * @return string字符串一维数组
     */
    public String[] addOpt (String num, int target) {
        char[] arr=num.toCharArray();
        int n=num.length();
        List<String> res=new ArrayList<>();
        //利用位运算向字符串中添加运算符（"+"、"-"、"*"）
        for(int mask=0;mask<(1<<(2*n-2));mask++){
            //临时可变字符串，用于存储表达式
            StringBuilder sb=new StringBuilder();
            //添加第一个数字
            sb.append(arr[0]);
            for(int i=n-1;i>=1;i--){
                //t1、t2可以判断对应高位、低位（用h、l表示）是0还是1
                int t1=mask&(1<<(2*i-1));
                int t2=mask&(1<<(2*i-2));
                //说明h为0、l为0，不添加运算符
                if(t1==0&&t2==0){
                    sb.append(arr[i]);
                }
                //说明h为0、l为1，添加"+"运算符
                if(t1==0&&t2!=0){
                    sb.append("+");
                    sb.append(arr[i]);
                }
                //说明h为1、l为0，添加"-"运算符
                if(t1!=0&&t2==0){
                    sb.append("-");
                    sb.append(arr[i]);
                }
                //说明h为1、l为1，添加"*"运算符
                if(t1!=0&&t2!=0){
                    sb.append("*");
                    sb.append(arr[i]);
                }
            }
            String s=sb.toString();
            //如果不包含前导0，并且表达式的值等于target，则加入到res
            if(check(s)&&cal(s)==(long)target){
                res.add(s);
            }
        }
        return res.toArray(new String[res.size()]);
    }
    
    //检查前导0
    private boolean check(String s){
        int n=s.length();
        char[] arr=s.toCharArray();
        for(int i=0;i<n-1;i++){
            //当前位置是0
            if(arr[i]=='0'){
                //如果是第1位，或者前面不包含数字
                if(i==0||!Character.isDigit(arr[i-1])){
                    //而后面包含数字，则属于前导0
                    if(Character.isDigit(arr[i+1])){
                        return false;
                    }
                }
            }
        }
        return true;
    }

    //计算表达式的值
    private long cal(String s) {
        int n=s.length();
        Deque<Long> stack=new LinkedList<>();
        //初始化符号
        char sign='+';
        long num=0;
        for(int i=0;i<n;i++){
            //计算当前数字的值
            if(s.charAt(i)>='0'&&s.charAt(i)<='9'){
                num=num*10+s.charAt(i)-'0';
            }         
            //如果不是数字
            if(!Character.isDigit(s.charAt(i))||i==n-1){
                //将带符号的数字加入到栈中
                switch(sign){
                    case '+':
                        stack.push(num);
                        break;
                    case '-':
                        stack.push(-num);
                        break;
                    case '*':
                        stack.push(stack.pop()*num);
                        break;                     
                }
                //更新当前符号
                sign=s.charAt(i);
                //num重置为0
                num=0;
            }
            
            
        }
        long res=0;
        //将栈中所有的数字相加即可得到结果
        while(!stack.isEmpty()){
            res+=stack.pop();
        }
        return res;
    }
}

3.复杂度分析

• 时间复杂度：总共要遍历$4^{(n-1)}4^\{(n-1)\}$个mask位，而每一个mask位对应$n-1n-1$个空位，需要考虑是否将运算符加入到空位，检查前导0和计算表达式值的复杂度为$O(n)O(n)$，所以时间复杂度是$O(n\ast 4^n)O(n*4^n)$。
• 空间复杂度：计算表达式的值时，需要额外大小为n的栈，所以空间复杂度为$O(n)O(n)$。

方法二（递归）

1.解题思路

• 利用递归逐位地进行遍历，遍历到字符串末尾，则终止递归。如果值为target，则加入到结果中。
• 遍历过程中计算当前可能的数字的值，然后添加"+"、添加"-"、添加"*"。如果是第一位，只需添加数字即可。这个过程中维护四个遍历，一个是字符串游标index（表示每次数字开头的索引），一个是当前带符号的数字cur，一个是当前表达式的值val，一个是当前表达式s。
• 如果遇到前导0，直接终止循环。如果是"+"或者"-"，直接更新对应的变量即可。如果是"*"，需要做特殊处理，因为乘法优先级高于加减法，所以当前带符号的数字更新为cur*number，表达式的值需要减去上一个cur，然后加上当前带符号的cur，即val-cur+cur*number。

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num string字符串 
     * @param target int整型 
     * @return string字符串一维数组
     */
    //记录结果
    List<String> res;
    //字符串长度
    int n;
    //数字字符串
    String num;
    //目标值
    int target;
    
    public String[] addOpt (String num, int target) {
        //初始化
        this.res=new ArrayList<>();
        this.num=num;
        this.n=num.length();
        this.target=target;
        //递归
        dfs(0,0,0,"");    
        return res.toArray(new String[res.size()]);
    }
    
    //index是游标、cur是带符号的当前数字、val为当前表达式的值，s为当前表达式
    private void dfs(int index,long cur,long val,String s){
        //到达字符串末尾，递归终止
        if(index==n){
            //如果等于target，就加入到结果中
            if(val==target){
                res.add(s);
            }
            return;
        }
        //计算当前待确定的数字的值
        long number=0;
        for(int i=index;i<n;i++){
            //如果不是第一位，并且当前位是0，说明含前导零，终止循环
            if(i!=index&&num.charAt(index)=='0') break;
            //计算number
            number=number*10+num.charAt(i)-'0';
            //如果是表达式的第1位，直接加入number
            if(index==0){
                dfs(i+1,number,number,""+number);
            }
            else{
                //当前字符串s加上对应符号（"+"、"-"、"*"），以及number
                dfs(i+1,number,val+number,s+"+"+number);
                dfs(i+1,-number,val-number,s+"-"+number);
                //乘法优先级高于加减法，所以要减去上一次的cur，再加上当前带符号的cur
                dfs(i+1,cur*number,val-cur+cur*number,s+"*"+number);
            }
        }
    }
}

3.复杂度分析

• 时间复杂度：假设字符串总长度为n，最坏情况下，需要在其中n-1个空中添加运算符，每一个空对应不添加、添加"+"、添加"-"、添加"*"四种选择，总共有$4^{n-1}4^\{n-1\}$种选择，所以时间复杂度是$O(4^n)O(4^n)$。
• 空间复杂度：递归栈的深度为n，所以空间复杂度为$O(n)O(n)$。