Simple Java recursive solution with memoization. Beat 82%


  • 2

    First of all, I noticed that many people confuse "memoization" with "memorization".
    https://en.wikipedia.org/wiki/Memoization
    "In computing, memoization is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again. "
    https://www.topcoder.com/community/data-science/data-science-tutorials/an-introduction-to-recursion-part-2/

    The reason to use memo is we don't want to solve the same subproblem over and over again. For example, if input is "2 * 3+7-1". "2 * 3" will be calculated twice when we break input at "+" and "-". When using memoization, the recursive method is always bottom to top, so that you can store the solutions to smaller problems and reuse them.

    public class Solution {
        public List<Integer> diffWaysToCompute(String input) {
            Map<String, List<Integer>> memo = new HashMap<>();
            return search(input, memo);
        }
        
        private List<Integer> search(String input, Map<String, List<Integer>> memo) {
            if (memo.containsKey(input)) {
                return memo.get(input);
            }
            
            List<Integer> res = new ArrayList<>();
            
            char[] chrs = input.toCharArray();
            for (int i = 0; i < chrs.length; i++) {
                char chr = chrs[i];
                if (!Character.isDigit(chr)) {
                    for (int l : search(input.substring(0, i), memo)) {
                        for (int r : search(input.substring(i + 1), memo)) {
                            res.add(chr == '+' ? l + r : chr == '-' ? l - r : l * r);
                        }
                    }
                }
            }
            
            if (res.isEmpty()) {
                res.add(Integer.parseInt(input));
            }
            
            memo.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.