Share my Finite-State Machine solution with detailed state transition table


  • 0
    F
    Legend:
        d: 0~9
        +: +/-
        END: '\0'
        "": white space 
        F: from state
        C: seeing character c
        T: to state
    State transition table:
            F   C   T
            0	“”	0
            0	+	1
            0	d	2
            0	.	3
            0	END	false
            1	d	2
            1	.	3
            1	END	false
            2	d	2
            2	.	4
            2	e	5
            2	END	true
            2	“”	8
            3	d	4
            4	e	5
            4	d	4
            4	END	true
            4	“”	8
            5	d	6
            5	+	7
            5	END	false
            6	d	6
            6	END	true
            6	“”	8
            7	d	6
            7	END	false
            8	“”	8
            8	END	true
    
     State meaning:         		
            1: have seen +-
            2: have seen at least 1 number after + -
            3: have seen .dot and no number before .dot
            4: have seen .dot and at least one number 
            5: have seen e
            6: have seen one number after e
            7: have seen +/- after e
            8: have seen a valid number, parsing “ “
            9: true;
            -1: false
        
        //////////////////////Code starts here://///////////////////
    class Solution {
        //d 3 
        //' ' 4;
        //e  2
        // . 1
        //+  0
        //\0 5
        inline int c_type(char c)
        {
            return (c == '+' || c == '-' ) ? 0 : c == '.' ? 1 : (c == 'e' || c == 'E') ? 2 : (c >= '0' && c <= '9') ? 3 : (c == ' ') ?  4 : c == '\0' ? 5 : 6;
        }
    public:
        bool isNumber(string s) {
            s.push_back('\0');
            int fsm[9][7];
            memset(fsm, -1, sizeof(fsm)); 
            fsm[0][4] = 0;
            fsm[0][0] = 1;
            fsm[0][3] = 2;
            fsm[0][1] = 3;
            fsm[0][5] = -1;
            fsm[1][3] = 2;
            fsm[1][1] = 3;
            fsm[1][5] = -1;
            fsm[2][3] = 2;
            fsm[2][1] = 4;
            fsm[2][2] = 5;
            fsm[2][4] = 8;
            fsm[2][5] = 9;
            fsm[3][3] = 4;
            fsm[4][2] = 5;
            fsm[4][3] = 4;
            fsm[4][4] = 8;
            fsm[4][5] = 9;
            fsm[5][3] = 6;
            fsm[5][0] = 7;
            fsm[5][5] = -1;
            fsm[6][3] = 6;
            fsm[6][5] = 9;
            fsm[6][4] = 8;
            fsm[7][3] = 6;
            fsm[7][5] = -1;
            fsm[8][4] = 8;
            fsm[8][5] = 9;
            int state = 0;
            for (int i = 0; i < s.size(); ++i)
            {
               state = fsm[state][c_type(s[i])];
               if(state == -1)
                    return false;
                if(state == 9)
                    return true;
            }
            return "This return will never be reached but can't be deleted or compiler complains!";
        }
    };

Log in to reply
 

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