Valid Number - By DFA

Introduction to the Problem

The question asks the programmer to validate whether a string is a valid representation of a number. After some trials, we find that the question accepts a few formats:

1. pure integer
2. real number (decimal representation), including omitted zero, for example “.5”, “12.”
3. scientific number, that looks like “{Real Number}e{Integer}”
4. integer and real number can be signed
5. ignore any surrounding white spaces

In order to solve the problem in linear time, most solutions set a few flags. This is simple, and quite efficient in both time and space. In fact, I don’t really consider this problem qualified for hard.

Just to add some fun, this problem can be solved using a very textbook DFA. The code is elegant, less space efficient (but only for a constant amount) than the flag algorithm. In fact, the latter is just a compact, specialized DFA in essence. The trade-off is more variables and branching.

The Algorithm

The first step, we trim the string. There is probably not efficient in bringing white space processing into the DFA.

static inline string trim(string s)
{
    if (s.size() == 0) return s;

    char *c = &(s[0]), // starting pointer
         *d = c + s.length() - 1; // ending pointer

    while (*c != '\0' && isspace(*c)) c++;
    while (d != c && isspace(*d)) d--;

    *(d + 1) = '\0';

    return string(c);
}

DFA - States

Any accepted string can be divided into a few parts:

1. before decimal, the left part of a real number
2. decimal
3. after decimal, the right part of a real number
4. e character
5. the exponent, the right to ’e'

Any part could potentially empty. The (1) and (5) could potentially be preceded with a sign (’+’ or ‘-’).

Then, we can collect all states based on the grammar:

The starting state is START.

FAULT is a special state, that the DFA will halt whenever it meets FAULT, so that we do not have to process the rest of the string.

DFA - Transition

The transition function is a matrix that maps (state, input char) to state.

DFA - Termination

The DFA will terminate when

• input is depleted
• state is FAULT

The string will be accepted if the termination state is one of following:

• REALLEFT
• REALRIGHT
• ERIGHT
• DOT

In all other cases, the format is somewhat faulty. For example, if the DFA ended at E, then the string looks like "{some number}e", which is not acceptable.

The running of the DFA is easy. Simply iterate over the input, and let the transition matrix do its magic.

Complete Code:

class Solution {

    static inline string trim(string s)
    {
        if (s.size() == 0) return s;

        char *c = &(s[0]),
             *d = c + s.length() - 1;
        while (*c != '\0' && isspace(*c))
            c++;

        while (d != c && isspace(*d))
            d--;

        *(d + 1) = '\0';

        return string(c);
    }

    int START = 0;
    int REALLEFT = 1;
    int DOT = 2;
    int E = 3;
    int REALRIGHT = 4;
    int DOT_E = 5;
    int ERIGHT = 6;
    int SIGN1 = 7;
    int SIGN2 = 8;
    int FAULT = -1;

    int DIGIT = 0;
    int NDIGIT = 4;
    int SIGN = 1;

    int G[45] =
    {//  DIGIT       SIGN    DOT      E     NDIGIT
        REALLEFT,   SIGN1,  DOT_E,  FAULT,  FAULT,
        REALLEFT,   FAULT,  DOT,    E,      FAULT,
        REALRIGHT,  FAULT,  FAULT,  E,      FAULT,
        ERIGHT,     SIGN2,  FAULT,  FAULT,  FAULT,
        REALRIGHT,  FAULT,  FAULT,  E,      FAULT,
        REALRIGHT,  FAULT,  FAULT,  FAULT,  FAULT,
        ERIGHT,     FAULT,  FAULT,  FAULT,  FAULT,
        REALLEFT,   FAULT,  DOT_E,  FAULT,  FAULT,
        ERIGHT,     FAULT,  FAULT,  FAULT,  FAULT
    };

public:
    bool isNumber(string s) {
        s = trim(s);

        if (s.size() == 0) return false;

        char prev = '\0';
        int state = START;

        for (auto c : s)
        {
            if (state == FAULT) return false;

            int ch = (isdigit(c)) ? DIGIT
                    : (c == '.')  ? DOT
                    : (c == 'e')  ? E
                    : (c == '+')  ? SIGN
                    : (c == '-')  ? SIGN
                    : NDIGIT;

            state = G[state * 5 + ch];
        }

        if (state == E || state == DOT_E || state == SIGN1 || state == SIGN2 || state == START || state == FAULT)
            return false;
        return true;
    }
};