Java recursive (9ms) and dp (4ms) solution


  • 34
    S

    I think it's more efficient to pre-parse the string because String.substring() is costly. I store the parsed string in a list, for example, if the string is 1+2+3+4, then the list will contain:

    "1", "+", "2", "+", "3", "+", "4"
    

    Personally I feel this is also more convenient because all integers occurs at even indices (0, 2, 4, 6) and all operators are at odd indices (1, 3, 5).

    Then the problem is very similar to "Unique Binary Search Trees II". For each operator in the list, we compute all possible results for entries to the left of that operator, which is List<Integer> left, and also all possible results for entries to the right of that operator, namely List<Integer> right, and combine the results. It can be achieved by recursion or more efficiently by dp.

    Recursion:

    public List<Integer> diffWaysToCompute(String input) {
        List<Integer> result=new ArrayList<>();
        if(input==null||input.length()==0)  return result;
        List<String> ops=new ArrayList<>();
        for(int i=0; i<input.length(); i++){
            int j=i;
            while(j<input.length()&&Character.isDigit(input.charAt(j)))
                j++;
            String num=input.substring(i, j);
            ops.add(num);
            if(j!=input.length())   ops.add(input.substring(j, j+1));
            i=j;
        }
        result=compute(ops, 0, ops.size()-1);
        return result;
    }
    private List<Integer> compute(List<String> ops, int lo, int hi){
        List<Integer> result=new ArrayList<>();
        if(lo==hi){
            Integer num=Integer.valueOf(ops.get(lo));
            result.add(num);
            return result;
        }
        for(int i=lo+1; i<=hi-1; i=i+2){
            String operator=ops.get(i);
            List<Integer> left=compute(ops,lo, i-1), right=compute(ops, i+1, hi);
            for(int leftNum:left)
                for(int rightNum: right){
                    if(operator.equals("+"))
                        result.add(leftNum+rightNum);
                    else if(operator.equals("-"))
                        result.add(leftNum-rightNum);
                    else
                        result.add(leftNum*rightNum);
                }
        }
        return result;
    }
    

    And DP, where dp[i][j] stores all possible results from the i-th integer to the j-th integer (inclusive) in the list.

    public List<Integer> diffWaysToCompute(String input) {
        List<Integer> result=new ArrayList<>();
        if(input==null||input.length()==0)  return result;
        List<String> ops=new ArrayList<>();
        for(int i=0; i<input.length(); i++){
            int j=i;
            while(j<input.length()&&Character.isDigit(input.charAt(j)))
                j++;
            ops.add(input.substring(i, j));
            if(j!=input.length())   ops.add(input.substring(j, j+1));
            i=j;
        }
        int N=(ops.size()+1)/2; //num of integers
        ArrayList<Integer>[][] dp=(ArrayList<Integer>[][]) new ArrayList[N][N];
        for(int d=0; d<N; d++){
            if(d==0){
                for(int i=0; i<N; i++){
                    dp[i][i]=new ArrayList<>();
                    dp[i][i].add(Integer.valueOf(ops.get(i*2)));
                }
                continue;
            }
            for(int i=0; i<N-d; i++){
                dp[i][i+d]=new ArrayList<>();
                for(int j=i; j<i+d; j++){
                    ArrayList<Integer> left=dp[i][j], right=dp[j+1][i+d];
                    String operator=ops.get(j*2+1);
                    for(int leftNum:left)
                        for(int rightNum:right){
                            if(operator.equals("+"))
                                dp[i][i+d].add(leftNum+rightNum);
                            else if(operator.equals("-"))
                                dp[i][i+d].add(leftNum-rightNum);
                            else
                                dp[i][i+d].add(leftNum*rightNum);
                        }
                }
            }
        }
        return dp[0][N-1];
    }

  • 0
    Y

    Very nice and clean thoughts!


  • 0
    F

    Very clean DP solution and indeed, pre-parsing make it faster than substring.


  • 1
    V

    What happens when there's a number of more than 1 digit?


  • 0

    @SylvanasWindrunner said in Java recursive (9ms) and dp (4ms) solution:

    Personally I feel this is also more convenient because all integers occurs at even indices (0, 2, 4, 6) and all operators are at odd indices (1, 3, 5).

    Great solution. I think you should edit away this line though. Neither is this line right nor is it reflected in your actual code.


Log in to reply
 

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