This is the 17th day of my participation in the Genwen Challenge

Topic describes

Significant numbers (in order) can be broken down into the following parts:

A decimal or integer (optional) an 'e' or an 'e' followed by an integerCopy the code

Decimals (in order) can be divided into the following parts:

(Optional) A symbolic character ('+' 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 digitCopy the code

Integers (in order) can be divided into the following parts:

(Optional) A symbolic character ('+' or '-') with at least one digitCopy the code

Some significant figures are listed below:

[" 2 ", "0089", "0.1", "+ 3.14", "4", "- 9", "2 e10", "- 90 e3", "3 e + 7", "+ 6 e - 1", "53.5 e93", "123.456 e789"]Copy the code

Some invalid numbers are listed below:

[" ABC ", "1 a", "1 e", "e3", "99 e2. 5", "- 6", "- + 3", "95 a54e53"]Copy the code

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

Example 1:

Input: s = 0 Output: trueCopy the code

Example 2:

Input: s = "e" Output: falseCopy the code

Example 3:

Input: s = "." Output: falseCopy the code

Example 4:

Input: s = ".1" Output: trueCopy the code

Tip:

  • 1 < =s.length< = 20
  • sContains only letters (uppercase and lowercase), digits (0-9), plus ‘+’, minus ‘-‘, or the dot ‘.’.

Their thinking

Finite state machine solution

1: Initial state (empty string or pure space)

2: the sign bit

3: digit bit (such as -164, can be used as an end)

4: the decimal point

5: The number after the decimal point (.721 or -123.6 can be used as an end)

6: index e

7: the sign bit after the exponent

8: The number following the exponent (such as +1e-6, can be used as an end)

9: state 3,5,8 with extra space (mainly to judge “1, 1” is not reasonable)

code

class Solution:
    def isNumber(self, s: str) - >bool:
        # DFA transitions: dict[action] -> successor
        states = [{},
                  # state 1
                  {"blank":1."sign":2."digit":3."dot":4},
                  # state 2
                  {"digit":3."dot":4},
                  # state 3
                  {"digit":3."dot":5."e|E":6."blank":9},
                  # state 4
                  {"digit":5},
                  # state 5
                  {"digit":5."e|E":6."blank":9},
                  # state 6
                  {"sign":7."digit":8},
                  # state 7
                  {"digit":8},
                  # state 8
                  {"digit":8."blank":9},
                  # state 9
                  {"blank":9}]

        def strToAction(st) :
            if '0' <= st <= '9':
                return "digit"
            if st in "+ -":
                return "sign"
            if st in "eE":
                return "e|E"
            if st == '. ':
                return "dot"
            if st == ' ':
                return "blank"
            return None

        currState = 1
        for c in s:
            action = strToAction(c)
            if action not in states[currState]:
                return False
            currState = states[currState][action]

        # ending states: 3,5,8,9
        return currState in {3.5.8.9}
Copy the code