HARD

Valid Number

A valid number can be split up into these components (in order):

A decimal number or an integer.
(Optional) An 'e' or 'E', followed by an integer.

A decimal number can be split up into these components (in order): - (Optional) A sign character (either '+' or '-'). - One of the following formats: - At least one digit, followed by a dot '.' - At least one digit, followed by a dot '.', followed by at least one digit - A dot '.', followed by at least one digit

An integer can be split up into these components (in order): - (Optional) A sign character (either '+' or '-'). - At least one digit

Return true if s is a valid number.

Example

Input:

s = "0"

Output:

true

Input:

s = "e"

Output:

false

Input:

s = ".1"

Output:

true

Constraints

1 ≤ s.length ≤ 20
s consists of only English letters (both uppercase and lowercase), digits (0-9), plus '+', minus '-', or dot '.'

Solution: State Machine

Time Complexity: O(n)
Space Complexity: O(1)

C++

class Solution {
public:
    bool isNumber(string s) {
        // This is the DFA we have designed above
        map<string, int> dfa[8] = {{{"digit", 1}, {"sign", 2}, {"dot", 3}},
                                   {{"digit", 1}, {"dot", 4}, {"exponent", 5}},
                                   {{"digit", 1}, {"dot", 3}},
                                   {{"digit", 4}},
                                   {{"digit", 4}, {"exponent", 5}},
                                   {{"sign", 6}, {"digit", 7}},
                                   {{"digit", 7}},
                                   {{"digit", 7}}};
        int current_state = 0;
        string group;
        for (char c : s) {
            if (isdigit(c)) {
                group = "digit";
            } else if (c == '+' || c == '-') {
                group = "sign";
            } else if (c == 'e' || c == 'E') {
                group = "exponent";
            } else if (c == '.') {
                group = "dot";
            } else {
                return false;
            }
            if (dfa[current_state].find(group) == dfa[current_state].end()) {
                return false;
            }
            current_state = dfa[current_state][group];
        }
        return current_state == 1 || current_state == 4 || current_state == 7;
    }
};