Leetcode Expression Add Operators problem solution

YASH PAL,

In this Leetcode Expression Add Operators problem solution we have given a string num that contains only digits and an integer target, return all possibilities to add the binary operators ‘+’, ‘-‘, or ‘*’ between the digits of num so that the resultant expression evaluates to the target value.

Leetcode Expression Add Operators problem solution

Problem solution in Python.

class Solution(object):
    def addOperators(self, num, target):
        """
        :type num: str
        :type target: int
        :rtype: List[str]
        """
        if not num:
            return []
        ans = [num[0]]
        ams = [[int(num[0])]]
        for n in range(1,len(num)):
            temp = []
            tenp = []
            for i,a in enumerate(ans):
                temp.append(a+"+"+num[n]);
                tenp.append(ams[i]+[int(num[n])])
                temp.append(a+"-"+num[n]);
                tenp.append(ams[i]+[-int(num[n])])
                
                temp.append(a+"*"+num[n]);
                tamsa = [b for b in ams[i]]
                tamsa[-1]*= int(num[n])
                tenp.append(tamsa)
                
                if a[-1]!= "0" or (len(a)>1 and a[-2].isalnum()):
                    temp.append(a+""+num[n]);
                    tams = [b for b in ams[i]]
                    tams[-1]= tams[-1]*10+int(num[n])
                    tenp.append(tams)
            ans = temp
            ams = tenp
            # print(ans, ams)
        aans = []
        for i,a in enumerate(ans):
            if sum(ams[i])==target:
                aans.append(a)
        return aans

Problem solution in Java.

class Solution {
    int n;
    String num;
    List<String> list;
    public List<String> addOperators(String num, int target) {
        n = num.length();
        this.num = num;
        list = new ArrayList<>();
        if(n>0){
            f(0,target,1,1,num.charAt(0)-'0',"" + num.charAt(0));
        }
        return list;
    }
    
    void f(int i,long target,int c,long x,long y,String expr){
        if(i==n-1){
            if(target == c*x*y){
                list.add(expr);
            }
            return;
        }
        int p = num.charAt(i+1) - '0';
        long prd = y*x;
        f(i+1,target             ,c,prd,p,expr + "*" + num.charAt(i+1));
        f(i+1,target - prd*c,1,    1,p,expr + "+" + num.charAt(i+1));
        f(i+1,target - prd*c,-1,   1,p,expr + "-" + num.charAt(i+1));
        if(y!=0){
            f(i+1,target, c,x, 10*y + p,expr + num.charAt(i+1));
        }
    }
}

Problem solution in C++.

class Solution 
{
public:    
    vector<string> addOperators(string num, long long target) 
    {
        _number = std::move(num);
        
        if (!_number.empty())
        {
            _buffer.resize(_number.size());
            tryAddSymbol(0, 0, -target, 1, _number[0] - '0');
        }
        
        return move(_result);
    }
private:
    
    void addResultString()
    {
        string str;
        for (size_t i = 0; i < _buffer.size(); ++i)
        {
            if (_buffer[i])
            {
                str += _buffer[i];
            }
            str += _number[i];
        }
        _result.push_back(std::move(str));
    }
    
    void tryAddSymbol(char symbol, size_t index, long long value1, long long value2, long long value3)
    {
        _buffer[index++] = symbol;
        if (index != _number.size())
        {
            const auto digit = _number[index] - '0';
            tryAddSymbol('+', index, value1 + value2 * value3, 1, digit);
            tryAddSymbol('-', index, value1 + value2 * value3, -1, digit);
            tryAddSymbol('*', index, value1, value2 * value3, digit);
            if (value3)
            {
                tryAddSymbol('', index, value1, value2, 10 * value3 + digit);
            }
        }
        else if (value1 + value2 * value3 == 0)
        {
            addResultString();
        }
    }
    
private:
    
    std::string _number;
    std::vector<char> _buffer;
    vector<string> _result;
};

coding problems