Share a clean and short JAVA solution


  • 52
    W
    public class Solution {
        public List<Integer> diffWaysToCompute(String input) {
            List<Integer> res = new ArrayList<Integer>();
            for (int i = 0; i < input.length(); i++) {
                char c = input.charAt(i);
                if (c == '-' || c == '+' || c == '*') {
                    String a = input.substring(0, i);
                    String b = input.substring(i + 1);
                    List<Integer> al = diffWaysToCompute(a);
                    List<Integer> bl = diffWaysToCompute(b);
                    for (int x : al) {
                        for (int y : bl) {
                            if (c == '-') {
                                res.add(x - y);
                            } else if (c == '+') {
                                res.add(x + y);
                            } else if (c == '*') {
                                res.add(x * y);
                            }
                        }
                    }
                }
            }
            if (res.size() == 0) res.add(Integer.valueOf(input));
            return res;
        }
    }

  • 3
    H

    Nice solution. The code is clean.

    Two more points. First, using a map to memorize the results of previous solved problems can help.

    Second, instead of checking the size of list in the end, I prefer to check if the input is digit or not. Which make the code more robust.

    public class Solution { 
        
        private Map<String,List<Integer>> memo = new HashMap<>();
        
        public List<Integer> diffWaysToCompute(String input) {
            int len = input.length();
            // check history
            List<Integer> result = memo.get(input);
            if (result != null) { return result; }
            result = new ArrayList<>();
            // base case
            if (isDigit(input)) {
                result.add(Integer.parseInt(input));
                memo.put(input,result);
                return result;
            }
            // recursion (divid & conquer)
            for (int i = 0; i < len; 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,len));
                    for (Integer il : left) {
                        for (Integer ir : right) {
                            switch (c) {
                                case '+': result.add(il + ir); break;
                                case '-': result.add(il - ir); break;
                                case '*': result.add(il * ir); break;
                            }
                        }
                    }
                }
            }
            memo.put(input,result);
            return result;
        }
        private boolean isDigit(String s) {
            for (Character c : s.toCharArray()) {
                if (!Character.isDigit(c)) { return false; }
            }
            return true;
        }
    }

Log in to reply
 

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