Recursive solution out of memory. :(


  • 0
    X
    public static long calculate(String s) {
        s=s.replace(" ","");
        int lastpos = -1;
        char lastOps = ' ';
        for (int i = s.length() - 1; i >= 0; i--) {
            switch (s.charAt(i)) {
            case '+':
                return calculate(s.substring(0, i)) + calculate(s.substring(i + 1, s.length()));
            case '-':
                return calculate(s.substring(0, i)) - calculate(s.substring(i + 1, s.length()));
            case '*':
                if (lastpos < 0) {
                    lastpos = i;
                    lastOps = '*';
                }
                break;
            case '/':
                if (lastpos < 0) {
                    lastpos = i;
                    lastOps = '/';
                }
                break;
            }
        }
        if (lastOps == '*') {
            return calculate(s.substring(0, lastpos)) * calculate(s.substring(lastpos + 1, s.length()));
        }
        if (lastOps == '/') {
            return calculate(s.substring(0, lastpos)) / calculate(s.substring(lastpos + 1, s.length()));
        }
        return Long.parseLong(s);
    }

  • 0

    Please try again, I have increased the memory limit. However it still complains about OutOfMemoryError: Java heap space. Well, at least you get to see the largest test case and try to debug it yourself.

    I guess your recursion went too deep and cause the heap space to run out. Also try to avoid using substring if possible, you can just pass in the indices to avoid copying the string many times.


  • 0
    S

    Hi~ I tried python recursion and also get recursion depth exceeded. Can you check whether a recursion solution can pass the OJ or not? I only used indices to indicate substring (rather than creating new substring) so that shouldn't be a problem.


Log in to reply
 

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