My Recursive FSM Solution

• 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);
}
}``````

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