My Recursive FSM Solution


  • 0
    S

    I set up my solution like a Finite State Machine. If you think of parsing the integer as a graph, each node has it's own method. Obviously, given the number of function calls, there will be a lot of overhead. But the process is conceptually straightforward.

    Does anyone know how I could improve efficiency but still keep the same design?

    import static java.lang.Character.isDigit;
    import static java.lang.Character.isWhitespace;
    
    public class Solution {
        public int myAtoi(String str) {
            return (int) atoi(str);
        }
    
        private static long atoi(String string) {
            return atoi(string, 0, 0);
        }
    
        private static long atoi(String str, int idx, long store) {
            return whiteSpace(str, idx, store);
        }
    
        private static long whiteSpace(String str, int idx, long store) {
            if (idx == str.length()) {
                return fail();
            }
    
            final char ch = str.charAt(idx);
    
            if (isWhitespace(ch)) {
                return whiteSpace(str, idx + 1, store);
            }
    
            if (ch == '-') {
                return negative(str, idx + 1, store);
            }
    
            if (ch == '+') {
                return positive(str, idx + 1, store);
            }
    
            if (isDigit(ch)) {
                return number(str, idx + 1, appendDigit(store, ch));
            }
    
            return fail();
        }
    
        private static long negative(String str, int idx, long store) {
            if (idx == str.length()) {
                return fail();
            }
    
            if (str.charAt(idx) == '0') {
                return leadingZero(str, idx + 1, store, true);
            }
    
            if (isDigit(str.charAt(idx))) {
                return number(str, idx + 1, -appendDigit(store, str.charAt(idx)));
            }
    
            return fail();
        }
    
        private static long positive(String str, int idx, long store) {
            if (idx == str.length()) {
                return fail();
            }
    
            if (str.charAt(idx) == '0') {
                return leadingZero(str, idx + 1, store, false);
            }
    
            if (isDigit(str.charAt(idx))) {
                return number(str, idx + 1, appendDigit(store, str.charAt(idx)));
            }
    
            return fail();
        }
    
        private static long leadingZero(String str, int idx, long store, boolean isNeg) {
            if (idx == str.length()) {
                return success(store);
            }
    
            if (str.charAt(idx) == '0') {
                return leadingZero(str, idx + 1, store, isNeg);
            }
    
            if (isDigit(str.charAt(idx))) {
                if (isNeg) {
                    return number(str, idx + 1, -Character.getNumericValue(str.charAt(idx)));
                }
    
                return number(str, idx + 1, Character.getNumericValue(str.charAt(idx)));
            }
    
            return success(0);
        }
    
        private static long number(String str, int idx, long store) {
            if (Integer.MAX_VALUE < store) {
                return overflow();
            }
    
            if (Integer.MIN_VALUE > store) {
                return underflow();
            }
    
            if (idx == str.length()) {
                return success(store);
            }
    
            if (isDigit(str.charAt(idx))) {
                return number(str, idx + 1, appendDigit(store, str.charAt(idx)));
            }
    
            return success(store);
        }
    
        private static long fail() {
            return 0;
        }
    
        private static long success(long store) {
            return store;
        }
    
        private static long overflow() {
            return (long) Integer.MAX_VALUE;
        }
    
        private static long underflow() {
            return (long) Integer.MIN_VALUE;
        }
    
        private static long appendDigit(long store, char ch) {
            if (store < 0) {
                return store * 10 + -Character.getNumericValue(ch);
            }
    
            return store * 10 + Character.getNumericValue(ch);
        }
    }

Log in to reply
 

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