Java solution, 4ms beats over 80%


  • 0

    Just sharing my solution, simple recursion + memorization. Any suggestions would be appreciated.

    public class Solution {
        public List<Integer> diffWaysToCompute(String input) {
            HashMap<String,List<Integer>> map = new HashMap<String,List<Integer>>();
            return helper(input,map);
        }
        
        public List<Integer> helper(String input, Map<String,List<Integer>> map) {
            if(map.containsKey(input)) return map.get(input);
            List<Integer> res = new ArrayList<Integer>();
            int len = input.length();
            boolean num = true;
            for(int i=0; i<len; i++){
                char c = input.charAt(i);
                if(c=='+'||c=='-'||c=='*'){
                    num = false;
                    List<Integer> left = helper(input.substring(0,i),map);            
                    List<Integer> right = helper(input.substring(i+1,len),map);
                    for(int l:left){
                        for(int r:right){
                            if(c=='+') res.add(l+r);
                            if(c=='-') res.add(l-r);
                            if(c=='*') res.add(l*r);
                        }
                    }
                }
            }
            if(num){
                res.add(Integer.parseInt(input));
            }
            if(!map.containsKey(input)) map.put(input,res);
            return res;
        }
    }
    

Log in to reply
 

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