A recursive Java solution (284 ms)


  • 183
    2
    public class Solution {
        public List<Integer> diffWaysToCompute(String input) {
            List<Integer> ret = new LinkedList<Integer>();
            for (int i=0; i<input.length(); i++) {
                if (input.charAt(i) == '-' ||
                    input.charAt(i) == '*' ||
                    input.charAt(i) == '+' ) {
                    String part1 = input.substring(0, i);
                    String part2 = input.substring(i+1);
                    List<Integer> part1Ret = diffWaysToCompute(part1);
                    List<Integer> part2Ret = diffWaysToCompute(part2);
                    for (Integer p1 :   part1Ret) {
                        for (Integer p2 :   part2Ret) {
                            int c = 0;
                            switch (input.charAt(i)) {
                                case '+': c = p1+p2;
                                    break;
                                case '-': c = p1-p2;
                                    break;
                                case '*': c = p1*p2;
                                    break;
                            }
                            ret.add(c);
                        }
                    }
                }
            }
            if (ret.size() == 0) {
                ret.add(Integer.valueOf(input));
            }
            return ret;
        }
    }

  • 7

    Hi, 2guotou. Your idea is really clever and easy to understand, as well as your code. I rewrite it in C++ (well, just like translation). Hope it is Ok :-)

    class Solution { 
    public:
        vector<int> diffWaysToCompute(string input) {
            vector<int> outputs;
            int n = input.length();
            for (int i = 0; i < n; i++) {
                if (input[i] == '+' || input[i] == '-' || input[i] == '*') {
                    string left = input.substr(0, i);
                    string right = input.substr(i + 1, n - i - 1);
                    vector<int> lval = diffWaysToCompute(left);
                    vector<int> rval = diffWaysToCompute(right);
                    for (int l : lval) {
                        for (int r : rval) {
                            switch (input[i]) {
                                case '+':
                                    outputs.push_back(l + r);
                                    break;
                                case '-':
                                    outputs.push_back(l - r);
                                    break;
                                default:
                                    outputs.push_back(l * r);
                            }
                        } 
                    }
                }
            }
            if (outputs.empty())
                outputs.push_back(stoi(input));
            return outputs;
        }
    };

  • 0

    Did you reimplement stoi on purpose? And substr doesn't need the second parameter.


  • 0

    Hi, Stefan. I almost did not realize stoi. About substr, I guess the expression for right need not have the second parameter, but the expression for left still needs. Is that right? BTW, I have updated my code.


  • 0
    C
    This post is deleted!

  • 0
    R

    it is just the Catalan number, in wiki


  • 1
    E

    This is a nice and clean solution. However, note that there are many overlapping sub-problems, dynamic programming should be a potential way to improve the performance.


  • 0
    R

    Using a map to memorize would be better.


  • 0
    N

    Hi, doesn't empty string break the code?


  • 13
    I

    I wish one day I should write a code like this on my own .


  • 0
    M

    this solution may calculate the same expression several times


  • 34
    M

    This is a brilliant solution except that may calculate the same expression several times when input is same.
    I modify a little bit and use a HashMap to memorize results for an input

    public class Solution {
        
        Map<String, List<Integer>> map = new HashMap<>();
        
        public List<Integer> diffWaysToCompute(String input) {
            List<Integer> res = new ArrayList<>();
            for (int i = 0; i < input.length(); i++) {
                char c = input.charAt(i);
                if (c == '+' || c == '-' || c == '*') {
                    String p1 = input.substring(0, i);
                    String p2 = input.substring(i + 1);
                    List<Integer> l1 = map.getOrDefault(p1, diffWaysToCompute(p1));
                    List<Integer> l2 = map.getOrDefault(p2, diffWaysToCompute(p2));
                    for (Integer i1 : l1) {
                        for (Integer i2 : l2) {
                            int r = 0;
                            switch (c) {
                                case '+':
                                    r = i1 + i2;
                                    break;
                                case '-':
                                    r = i1 - i2;
                                    break;
                                case '*':
                                    r = i1 * i2;
                                    break;
                            }
                            res.add(r);
                        }
                    }
                }
            }
            if (res.size() == 0) {
                res.add(Integer.valueOf(input));
            }
            map.put(input, res);
            return res;
        }
    }

  • 1
    C

    what's the time complexity for this??thanks


  • 0
    S

    Good solution! one minor suggestion: changing LinkedList to ArrayList will improve decrease the runtime significantly.


  • 14
    R

    @2guotou

    Brilliant.
    I think this can be optimized with memorization, to save some duplicate recursive calls.
    Your original solution is 8ms.
    After optimization, it is 3 ms.

    Please find my optimization with Hashtable memorization below.

    public class Solution {
        public List<Integer> diffWaysToCompute(String input) {
            return dfs(input, new HashMap<String, List<Integer>>());
        }
        
        private List<Integer> dfs(String input, Map<String, List<Integer>> map){
            if(map.containsKey(input)) return map.get(input);
            
            List<Integer> result = new ArrayList<>();
            for(int i=0;i<input.length();i++){
                char curChar = input.charAt(i);
                if(curChar == '+' || curChar == '-' || curChar == '*'){
                    String leftPart = input.substring(0,i);
                    String rightPart = input.substring(i+1);
                    List<Integer> leftResult = dfs(leftPart, map);
                    List<Integer> rightResult = dfs(rightPart, map);
                    for(Integer left: leftResult){
                        for(Integer right: rightResult){
                            int curResult = 0;
                            switch (curChar){
                                case '+':
                                    curResult = left + right;
                                    break;
                                case '-':
                                    curResult = left - right;
                                    break;
                                case '*':
                                    curResult = left * right;
                                    break;
                            }
                            result.add(curResult);
                        }
                    }
                }
            }
            
            if(result.size() == 0){
                    result.add(Integer.parseInt(input));
            }
            
            map.put(input, result);
            return result;
        }
    }
    
    

  • 0
    R

    @1337c0d3r Sure and done


  • 1
    H

    @ran3 What would be the time complexity for the solution?


  • 0
    D

    @ran3 Good idea, the longer the string, the more time saved.


  • 0
    I

    So the time complexity would be O(n^3)?


  • 0

    Very nice base case handle and the use of hashmap cache of sub-problem solution. Thanks for sharing!


Log in to reply
 

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