Show an answer using DFA (Deterministic Finite Automaton)


  • 2
    Z

    We can solve this problem with a dfa. In my opinion, there are 11 different statuses. For each status, there are 6 out edges at most, which are space, '+' or '-', '.' ,'e' , '0'~'9', and other characters. So, we can link these statuses by considering 6 out edges at most. Here is my solution with a DFA.

    class Solution {
    public:
        bool isNumber(const char *s) {
            int move[15][256]={0};
    
        /* 15 stands for the number of status ( 11, exactly) . 
    The default next status for each status is status 0, which means an infeasible final status. 
    256 stands for all the characters. 
    move[i][j]=k means if the current status is i, the status will change into k if an character j appears.
    The state transition table is shown as follows. */
                    
            move[1][' '] = 1;
            move[1]['+'] = 2;
            move[1]['-'] = 2;
            move[1]['.'] = 3;
            for(int i='0';i<='9';++i)move[1][i]=4;
            
            move[2]['.'] = 3;
            for(int i='0';i<='9';++i)move[2][i]=4;
            
            for(int i='0';i<='9';++i)move[3][i]=5;
            
            move[4]['e'] = 6;
            move[4]['.'] = 10;
            for(int i='0';i<='9';++i)move[4][i]=4;
            
            move[5]['e'] = 6;
            for(int i='0';i<='9';++i)move[5][i]=5;
            
            move[6]['+'] = 7;
            move[6]['-'] = 7;
            for(int i='0';i<='9';++i)move[6][i]=8;
            
            for(int i='0';i<='9';++i)move[7][i]=8;
            
            for(int i='0';i<='9';++i)move[8][i]=8;
            
            move[10]['e'] = 6;
            for(int i='0';i<='9';++i)move[10][i]=5;
            
            move[10][' '] = 9;
            move[4][' '] = 9;
            move[5][' '] = 9;
            move[8][' '] = 9;
            move[9][' '] = 9;
            
            /* Start with status 1. And we can scan the string only once.*/
            int status = 1;
            for(int i=0;s[i]!='\0';++i)
            {
                status = move[status][s[i]];
            }
    
            /* statuses 10, 4, 5, 8 and 9 are feasible final statuses */
            return status==10||status==4||status==5||status==8||status==9;
        }
    };

  • 1
    S

    That's definitely a nice thought. However, I find the code very hard to understand with so many magic numbers lying around. I suggest not using such a method in a real interview. It's hard for you to debug, and it's probably not the answer what most interviewers have in mind.


  • 0
    Z

    Yeah, I had drawn the status on my exercise book. So it's hard to imagine the total graph only by the state transition table. An efficient way is that, you can draw the graph, and the DFA will be more clear. Debugging is not hard , because we know the end status for each input string, and then we can add some essential edges or statuses to repair the DFA.


Log in to reply
 

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