2 Java solutions, recursion way & DP way, beat 98%


  • 0
    M
    1. Recusion way:

    Time Complexity: O(x^x), where x is the number of operators, which is at most n/2 -1. (n is the length of input string.)
    (If I'm wrong, please tell me. Thank you!)

    public class Solution {
        public List<Integer> diffWaysToCompute(String input) {
            return recursion(input);
        }
        
        private List<Integer> recursion(String input) {
            List<Integer> res = new ArrayList<>();
            for(int i=0; i<input.length(); i++){
                char c = input.charAt(i);
                if(c=='+'||c=='-'||c=='*'){
                    String str_left = input.substring(0, i);
                    String str_right = input.substring(i+1);
                    List<Integer> res_left = recursion(str_left);
                    List<Integer> res_right = recursion(str_right);
                    for(int left_val : res_left){
                        for(int right_val : res_right){
                            if(c=='+'){
                                res.add(left_val + right_val);
                            } else if(c=='-'){
                                res.add(left_val - right_val);
                            } else {
                                res.add(left_val * right_val);
                            }
                        }
                    }
                }
            }
            if(res.size()==0) res.add(Integer.valueOf(input));
            return res;
        }
    }
    
    1. DP way:

    Time Complexity: O(x^2 * y), where x is the number of operators, which is at most n/2 -1, and y is the size of output list.
    (If I'm wrong, please tell me. Thank you!)

    public class Solution {
        public List<Integer> diffWaysToCompute(String input) {
            final int N = input.length();
            List<Integer>[][] dp = new ArrayList[N][N];
            return recursion(input, 0, N-1, dp);
        }
        
        private List<Integer> recursion(String input, int start, int end, List<Integer>[][] dp) {
            if(dp[start][end]!=null) return dp[start][end];
            List<Integer> res = new ArrayList<>();
            for(int i=start; i<=end; i++){
                char c = input.charAt(i);
                if(c=='+'||c=='-'||c=='*'){
                    List<Integer> res_left = recursion(input, start, i-1, dp);
                    List<Integer> res_right = recursion(input, i+1, end, dp);
                    for(int left_val : res_left){
                        for(int right_val : res_right){
                            if(c=='+'){
                                res.add(left_val + right_val);
                            } else if(c=='-'){
                                res.add(left_val - right_val);
                            } else {
                                res.add(left_val * right_val);
                            }
                        }
                    }
                }
            }
            if(res.size()==0) res.add(Integer.valueOf(input.substring(start, end+1)));
            dp[start][end] = res;
            return res;
        }
    }
    

Log in to reply
 

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