Valid Number - DFA using hashmap

C++     Hard     Hash Table     String    

Problem Statement:

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

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

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

1. (Optional) A sign character (either '+' or '-').
2. One of the following formats:
   1. One or more digits, followed by a dot '.'.
   2. One or more digits, followed by a dot '.', followed by one or more digits.
   3. A dot '.', followed by one or more digits.

An integer can be split up into these components (in order):

1. (Optional) A sign character (either '+' or '-').
2. One or more digits.

For example, all the following are valid numbers: ["2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789"], while the following are not valid numbers: ["abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53"].

Given a string s, return true if s is a valid number.

 

Example 1:

Input: s = "0"
Output: true

Example 2:

Input: s = "e"
Output: false

Example 3:

Input: s = "."
Output: false

 

Constraints:

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

Solution:

Based on the problem statement, we construct the following DFA (deterministic finite automata) which is basically a state graph. If the input follows the state graph, it is a valid number.

The starting node is A and and the terminal nodes are double encircled.

For coding the solution, we use the same node names as given in the diagram. Edges can be either dig for digit, dot for dot, sig for sign and exp for small and capital E.

 
class Solution {
public:
    bool isNumber(string s) 
    {   
        unordered_map<char, unordered_map<string,char>> stateMap;
        stateMap['A'] = { {"dig",'B'}, {"dot",'C'}, {"sig",'D'} };
        stateMap['B'] = { {"dig",'B'}, {"dot",'E'}, {"exp",'F'} };
        stateMap['C'] = { {"dig",'E'} };
        stateMap['D'] = { {"dot",'C'}, {"dig",'B'} };
        stateMap['E'] = { {"dig",'E'}, {"exp",'F'} };
        stateMap['F'] = { {"dig",'G'}, {"sig",'H'} };
        stateMap['G'] = { {"dig",'G'} };
        stateMap['H'] = { {"dig",'G'} };
        char cur = 'A';
        for (char ch: s)
        {
            string state;
            if (ch>='0' && ch<='9') state="dig";
            else if (ch=='+' || ch=='-') state="sig";
            else if (ch=='e' || ch=='E') state ="exp";
            else if (ch=='.') state="dot";
            else return false;
            if (!stateMap[cur].count(state)) return false;
            cur = stateMap[cur][state];
        }
        return (cur=='B' || cur=='E' || cur=='G');
    }
};

 

If you are interested, I am adding code to run some tests:

 
class Solution {
public:
    bool isNumberUtil(string s)
    {
        unordered_map<char, unordered_map<string,char>> stateMap;
        stateMap['A'] = { {"dig",'B'}, {"dot",'C'}, {"sig",'D'} };
        stateMap['B'] = { {"dig",'B'}, {"dot",'E'}, {"exp",'F'} };
        stateMap['C'] = { {"dig",'E'} };
        stateMap['D'] = { {"dot",'C'}, {"dig",'B'} };
        stateMap['E'] = { {"dig",'E'}, {"exp",'F'} };
        stateMap['F'] = { {"dig",'G'}, {"sig",'H'} };
        stateMap['G'] = { {"dig",'G'} };
        stateMap['H'] = { {"dig",'G'} };
        char cur = 'A';
        for (char ch: s)
        {
            string state;
            if (ch>='0' && ch<='9') state="dig";
            else if (ch=='+' || ch=='-') state="sig";
            else if (ch=='e' || ch=='E') state ="exp";
            else if (ch=='.') state="dot";
            else return false;
            if (!stateMap[cur].count(state)) return false;
            cur = stateMap[cur][state];
        }
        return (cur=='B' || cur=='E' || cur=='G');
    }

    void runTests()
    {
        vector<string> tests{"2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789", "abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53"};
        for(string test: tests) cout<<test<<' '<< (isNumberUtil(test)?"TRUE":"FALSE" )<< endl;
    }

    bool isNumber(string s) 
    {   
        runTests();
        return isNumberUtil(s);
    }
};
 

You can see that all outputs are as expected.

 
2 TRUE
0089 TRUE
-0.1 TRUE
+3.14 TRUE
4. TRUE
-.9 TRUE
2e10 TRUE
-90E3 TRUE
3e+7 TRUE
+6e-1 TRUE
53.5e93 TRUE
-123.456e789 TRUE
abc FALSE
1a FALSE
1e FALSE
e3 FALSE
99e2.5 FALSE
--6 FALSE
-+3 FALSE
95a54e53 FALSE