Leetcode Different Ways to Add Parentheses problem solution

class Solution(object):
    def __init__( self):
        self.d = dict()
        
    def diffWaysToCompute(self, input):
        """
        :type input: str
        :rtype: List[int]
        """
        if input in self.d:
            return self.d[input]
        if input.isnumeric():
            return [ int(input) ]
        i = 0
        curr = ""
        res = []
        
        while( i < len( input ) ):
            if not input[i].isnumeric():
                x = self.diffWaysToCompute( curr )
                y = self.diffWaysToCompute( input[i+1:])
                for xi in x:
                    for yi in y:
                        if input[i] == "-":
                            res.append( xi-yi )
                        elif input[i] == "+":
                            res.append( xi+yi )
                        elif input[i] == "*":
                            res.append( xi*yi )
            curr += input[i] 
            i+=1
        self.d[input] = res
        return res

class Solution {
    Map<String, List<Integer>> cache;
    
    public List<Integer> diffWaysToCompute(String input) {
        //create cache
        cache = new HashMap<>(input.length()*input.length());
        
        return compute(input);
    }
    
    private List<Integer> compute(String string) {
        List<Integer> result = cache.get(string);
        if (result != null) 
            //return result from cache
            return result;
        
        result = new ArrayList<>();
        
        for (int pos = 0; pos < string.length(); pos++) {
            //trick to avoid mutiple comparisons with +/-/*
            if (string.charAt(pos) < '0') {
                List<Integer> leftList = compute(string.substring(0, pos));
                List<Integer> rightList = compute(string.substring(pos+1));
                
                for (int left : leftList) {
                    for (int right : rightList) {
                        
                        switch(string.charAt(pos)) {
                            case '-' : result.add(left-right); break;
                            case '+' : result.add(left+right); break;
                            case '*' : result.add(left*right); break;
                        }
                    
                    }
                }
            }
            
        }
        
        if (result.isEmpty()) result.add(Integer.valueOf(string));
        
        cache.put(string, result);
        return result;
    }
    
}

class Solution {
public:
vector<int> diffWaysToCompute(string input) {
    if(input.length()==0)return {};
    return helper(input, 0, input.length());
}
vector<int>helper(string str, int start, int end){
    vector<int>res, left, right;
    for(int i=start; i< end; i++ ){
        if(str[i]=='+'||str[i]=='-'||str[i]=='*'){
            left=helper(str, start, i);
            right=helper(str, i+1, end);
        for(auto & l :left)
            for(auto & r: right){
                if(str[i]=='+')res.push_back(l+r);
                else if(str[i]=='-')res.push_back(l-r);
                else res.push_back(l*r);
            }
        }
    }
    if(res.empty())res.push_back(stoi(str.substr(start, end-start+1)));

    return res;
}
};

int* diffWaysToCompute(char* input, int* returnSize) {
    int len=strlen(input);
    int *ret=(int*)calloc(2000,sizeof(int));
    int *left=NULL;
    int *right=NULL;
    int left_count=0;
    int right_count=0;
    *returnSize=0;
    int count=0;
    bool isNum=true;
    for(int i=0;i<len;i++){
        if(input[i]<'0'||input[i]>'9'){
            isNum=false;
            char temp=input[i];
            input[i]='';
            left=diffWaysToCompute(input,&left_count);
            right=diffWaysToCompute(&input[i+1],&right_count);
            for(int l=0;l<left_count;l++){
                for(int r=0;r<right_count;r++){
                    if(temp=='+'){
                        ret[(*returnSize)++]=left[l]+right[r];
                    }else if(temp=='-'){
                        ret[(*returnSize)++]=left[l]-right[r];
                    }else if(temp=='*'){
                        ret[(*returnSize)++]=left[l]*right[r];
                    }
                }
            }
            input[i]=temp;
        }
    }
    if(isNum){
         ret[(*returnSize)++]=atoi(input);
    }
    return ret;
}