Leetcode Different Ways to Add Parentheses problem solution

YASH PAL,

In this Leetcode Different Ways to Add Parentheses problem solution we have given a string expression of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. You may return the answer in any order.

Leetcode Different Ways to Add Parentheses problem solution

Problem solution in Python.

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

Problem solution in Java.

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;
    }
    
}

Problem solution in C++.

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;
}
};

Problem solution in C.

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;
}

coding problems