Using space to make it DP ( Java 6ms)


  • 0
    H

    Just a naive recursive approach but added an HashMap to prevent repeated operations. Suggestions are welcome :)

    public class Solution {
        Map<String,List<Integer>> map= new HashMap();
        public List<Integer> diffWaysToCompute(String input) {
            List<Integer> ans= new ArrayList();
            if(map.containsKey(input)){
                return map.get(input);
            }
            for(int i=0;i<input.length();i++){
                char c=input.charAt(i);
                if(c=='+' || c=='*' || c=='-'){
                    List<Integer> left= diffWaysToCompute(input.substring(0,i));
                    List<Integer> right= diffWaysToCompute(input.substring(i+1,input.length()));
                    for(Integer l:left){
                        for(Integer r:right){
                            switch(c){
                                case '+':
                                    ans.add(l+r); break;
                                case '-':
                                    ans.add(l-r); break;
                                case '*':
                                    ans.add(l*r); break;
                            }
                        }
                    }
                    
                }
            }
            if(ans.size()==0)
                ans.add(Integer.parseInt(input));
            
            map.put(input,ans);
                
            return ans;
        }
        
    }
    

Log in to reply
 

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