5ms java recursive with cache(hashmap)


  • 1
    S

    simple recursive (12ms) with optimize a little bit with cache (hashmap) (5ms)

    public class Solution {
    Set<Character> operators = new HashSet<Character>(Arrays.asList('+','-','*'));

    public List<Integer> diffWaysToCompute(String input) {
        Map<String, List<Integer>> cache = new HashMap<>(); 
        return diffWaysToCompute(input, cache);
    }
    
    private List<Integer> diffWaysToCompute(String input, Map<String, List<Integer>> cache) {
        if(cache.containsKey(input)) return cache.get(input); 
        
        List<Integer> vals = new ArrayList<Integer>(); 
        for(int i=0; i<input.length(); i++) { 
            if(!operators.contains(input.charAt(i))) continue; 
            
            char operator = input.charAt(i); 
            List<Integer> leftVals = diffWaysToCompute(input.substring(0,i), cache); 
            List<Integer> rightVals = diffWaysToCompute(input.substring(i+1), cache);
            
            for(Integer left : leftVals) { 
                for(Integer right : rightVals) { 
                    if(operator == '+') {
                        vals.add(left + right);
                    } else if(operator == '-') {
                        vals.add(left - right);
                    } else if(operator == '*') {
                        vals.add(left*right); 
                    }
                }
            }
        }
        
        // number only 
        if(vals.size() == 0) {
            vals.add(Integer.parseInt(input));
        }
        
        cache.put(input, vals);
        return vals; 
    }
    

    }


  • 0
    R

    aha..... I did similar solution. 5ms also.


Log in to reply
 

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