Recursive Java solution using Map!


  • 0
    S
    public class Solution {
        public List<Integer> diffWaysToCompute(String input) {
            if (input == null || input.length() < 1) {
                return new ArrayList<Integer>();
            }
            Map<String, List<Integer>> map = new HashMap();
            backtrack(input, 0, input.length() - 1, map);
            return map.get(input);
        }
        
        private List<Integer> backtrack(String str, int start, int end, Map<String, List<Integer>> map) {
            if (map.containsKey(str.substring(start, end + 1))) {
                return map.get(str.substring(start, end + 1));
            }
            // check if string is integer
            try {
                int val = Integer.parseInt(str.substring(start, end + 1));
                List<Integer> res = new ArrayList();
                res.add(val);
                map.put(str.substring(start, end + 1), res);
                return res;
            } catch (Exception e) {
                /* Ignore */
            }
            List<Integer> res = new ArrayList();
            for (int i = start + 1; i < end; i++) { // 1 + 2 - 3
                char ch = str.charAt(i);
                if (ch == '-' || ch == '+' || ch == '*') {
                    List<Integer> left = backtrack(str, start, i - 1, map);
                    List<Integer> right = backtrack(str, i + 1, end, map);
                    for (int ll : left) {
                        for (int rr : right) {
                            int result = 0;
                            if (ch == '+') {
                                result = ll + rr;
                            } else if (ch == '-') {
                                result = ll - rr;
                            } else {
                                result = ll * rr;
                            }
                            res.add(result);
                        }
                    }
                }
            }
            map.put(str.substring(start, end + 1), res);
            return res;
        }
    }
    

Log in to reply
 

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