Finite Automata Machine


  • 0
    J

    Maybe this method is not necessary in this question, but it is good to practice finite automata machine in order to solve more complicated problem.

    final int INVALID = 0; // other characters
    final int SPACE = 1;
    final int SIGN = 2;
    final int DIGIT = 3;
    
    public int myAtoi(String str) {
        
    	char[] charArr = str.toCharArray();
    	int i = 0;
    	double total = 0;
    	int sign = 1;
                // only two cases in this problem
    	int[][] machine = { // [curState][input]
    		{-1,0,1,1},  // 0: the init state or space
    		{-1,-1,-1,1}, // 1: digits or the second sign
    	};
    	int state = 0;
    	while (i < charArr.length) {
    		char c = charArr[i];
    		int input = INVALID;
    		if (c == ' ') input = SPACE;
    		else if (c == '+' || c == '-') input = SIGN;
    		else if (c >= '0' && c<= '9') input = DIGIT;
    		state = machine[state][input];
    		if (state == -1) break;
    		if (input == SIGN) sign = c=='-' ? -1 : 1;
    		if (input == DIGIT) {
    			total = total * 10 + (c - '0');
    			if (total*sign >= Integer.MAX_VALUE || total*sign <= Integer.MIN_VALUE)
    				return sign == -1 ? Integer.MIN_VALUE : Integer.MAX_VALUE;
    		}
    		i++;
    	}
    	return (int)total*sign;
    }

Log in to reply
 

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