My recursive java solution


  • 12
    L
    public class Solution {
    public List<Integer> diffWaysToCompute(String input) {
        List<Integer> list=new ArrayList();
        if(input==null||input.length()==0) return list;
        if(!input.contains("+")&&!input.contains("-")&&!input.contains("*")) {
            list.add(Integer.valueOf(input));
            return list;
        }
        for(int i=0;i<input.length();i++){
             char ops=input.charAt(i);
             if(ops=='+'||ops=='-'||ops=='*'){
                List<Integer> leftList=diffWaysToCompute(input.substring(0,i));
                List<Integer> rightList=diffWaysToCompute(input.substring(i+1,input.length()));
                for(int leftValue:leftList){
                    for(int rightValue:rightList){
                        switch(ops){
                            case '+': list.add(leftValue+rightValue); break;
                            case '-': list.add(leftValue-rightValue); break;
                            case '*': list.add(leftValue*rightValue); break;
                        }
                    }
                }
             }
          }
        return list;
    }
    

    }


  • 0
    P

    What is the complexity of this solution?


  • 0
    M

    @Pezhang

    @Pezhang said in My recursive java solution:

    complexity

    I think it is n!.
    For the first round, you have n-1 choices to combine any 2 numbers. In the second round, you have n-2 choices, .... So, it is: (n-1)(n-2)(n-3)....*1


  • 1

    Very concise solution. I came up with one similar with yours. But didn't implement it successfully. :/


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.