Java One Pass Recursion Method (3ms, beat 99%)


  • 7
    J
    public class Solution {
        public int calculate(String s) {
            if (s.length() == 0) return 0;
            return calculateHelper(s, 0, new int[]{s.length()});
        }
            
        private int calculateHelper(String s, int start, int[] end) {
            int sum = 0;
            int res = 0;
            char sign = '+';
            for (int i = start; i < end[0]; i++) {
                char temp = s.charAt(i);
                if (temp >= '0' && temp <= '9') {
                    sum = sum * 10 + (temp - '0');
                }
                if (temp == '+' || temp == '-' || temp == ')' || i == end[0] - 1) {
                    res = (sign == '+') ? res + sum : res - sum; 
                    if (temp != ')') sign = temp;
                    sum = 0;
                }
                // Return condition for recursion
                if (temp == ')' || i == end[0] - 1) {
                    end[0] = i;
                    return res;
                }
                if (temp == '(') {
                    int[] newEnd = {end[0]};
                    sum = calculateHelper(s, i + 1, newEnd);
                    if (newEnd[0] == end[0] - 1) {
                        res = (sign == '+') ? res + sum : res - sum; 
                    }
                    i = newEnd[0]; // Set i to the last recursion end point
                }
            }
            return res;
        }
    }
    

  • 0
    L

    @JaydenLYU Excellent solution! You use "int[] end" as a input/output parameter only -- set initial value of s.length and returns the end position of sub-expression.


Log in to reply
 

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