A dfa C solution.


  • 0
    M
    struct _State {
        struct _State* next[256];
    };
    typedef struct _State State;
    
    State* const ABT = (State*) 0;
    State* const ACC = (State*) 1;
    const int EOL = '\0';
    
    State* get_dfa_start() {
        static State states[9];
        static State *start;
    
        if (!start) {
            int ch;
            int i;
    
            i = 0;
            states[i].next[' '] = &states[0];
            states[i].next['.'] = &states[1];
            states[i].next['+'] = states[i].next['-'] = &states[2];
            for (ch = '0'; ch <= '9'; ch++) states[i].next[ch] = &states[3];
    
            i = 1;
            for (ch = '0'; ch <= '9'; ch++) states[i].next[ch] = &states[4];
    
            i = 2;
            states[i].next['.'] = &states[1];
            for (ch = '0'; ch <= '9'; ch++) states[i].next[ch] = &states[3];
    
            i = 3;
            states[i].next['.'] = &states[4];
            states[i].next['e'] = states[i].next['E'] = &states[5];
            states[i].next[' '] = &states[7];
            for (ch = '0'; ch <= '9'; ch++) states[i].next[ch] = &states[3];
            states[i].next[EOL] = ACC;
    
            i = 4;
            states[i].next['e'] = states[i].next['E'] = &states[5];
            states[i].next[' '] = &states[7];
            for (ch = '0'; ch <= '9'; ch++) states[i].next[ch] = &states[4];
            states[i].next[EOL] = ACC;
    
            i = 5;
            states[i].next['+'] = states[i].next['-'] = &states[6];
            for (ch = '0'; ch <= '9'; ch++) states[i].next[ch] = &states[8];
    
            i = 6;
            for (ch = '0'; ch <= '9'; ch++) states[i].next[ch] = &states[8];
    
            i = 7;
            states[i].next[' '] = &states[7];
            states[i].next[EOL] = ACC;
    
            i = 8;
            states[i].next[' '] = &states[7];
            for (ch = '0'; ch <= '9'; ch++) states[i].next[ch] = &states[8];
            states[i].next[EOL] = ACC;
    
            start = states;
        }
    
        return start;
    }
    
    bool isNumber(const char* s) {
        State *pstate = get_dfa_start();
        while (pstate != ABT && pstate != ACC) {
            pstate = pstate->next[(int)*s++];
        }
        return pstate == ACC;
    }
    

    Here is the DFA. Took me 3 hours to figure it out and draw it:
    DFA


Log in to reply
 

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