5 ms Java Solution using DP. (similar to Matrix multiplication)


  • 0
    D
    class Solution {
         public List<Integer> diffWaysToCompute(String input)  {
    
            String tokens[] = input.split("[-+*]");
            String operations[] = input.split("[0-9]+");
    
            List<Integer> [][] dp = new ArrayList[tokens.length][tokens.length];
    
    
            for (int i=0; i < dp.length; i++) {
                List<Integer> one = new ArrayList<>();
                one.add(Integer.parseInt(tokens[i]));
                dp[i][i] = one;
            }
    
            for (int steps=1; steps< dp.length; steps++) {
                int row=0;
                int col=steps;
    
                for(; row < dp.length && col < dp.length; row++, col++) {
                    List<Integer> list = new ArrayList<>();
                    for (int k=row; k < col; k++) {
                        List<Integer> left = dp[row][k];
                        List<Integer> right = dp[k+1][col];
                        for (int i=0; i < left.size(); i++) {
                            for (int j=0; j < right.size(); j++) {
                                list.add(cal(left.get(i), right.get(j), operations[k+1]));
                            }
                        }
                    }
                    dp[row][col]=list;
                }
            }
            return dp[0][dp[0].length-1];
        }
    
        public int cal(Integer first, Integer second, String operation )  {
            switch (operation) {
                case "+":
                    return first+ second;
                case "-":
                    return first-second;
                case "*":
                    return first * second;
            }
            return -1;
        }
    }
    

Log in to reply
 

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