題目

https://leetcode.com/problems/valid-number/description/

Given a string s, return whether s is a valid number.

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".

Formally, a valid number is defined using one of the following definitions:

  1. An integer number followed by an optional exponent.
  2. A decimal number followed by an optional exponent.

An integer number is defined with an optional sign '-' or '+' followed by digits.

A decimal number is defined with an optional sign '-' or '+' followed by one of the following definitions:

  1. Digits followed by a dot '.'.
  2. Digits followed by a dot '.' followed by digits.
  3. A dot '.' followed by digits.

An exponent is defined with an exponent notation 'e' or 'E' followed by an integer number.

The digits are defined as one or more digits.

  • 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 '.'.

一行 regex 的 C# 速解：

using System.Text.RegularExpressions;
public class Solution {
    
    public bool IsNumber(string s) {
        return Regex.IsMatch(s, @"^\s*[\-\+]?((\d+(\.\d*)?)|((\.\d+)))(e[\-\+]?\d+)?\s*$");
    }
}

不過這篇我是想要用有限狀態機來理解並且解出這題。

畫出轉移圖

1. integer

2. sign

3. decimal

4. exponent

程式碼

把圖所代表的狀態機代入 code 就可以完成這題了。轉移表的 row 是輸入類型，column 是狀態：

class Solution {
public:
    bool isNumber(string s) {
        enum Input { DIGIT, SIGN, DOT, EXP, INVALID };
        enum State {
            S0,  // START      尚未讀入任何字元
            S1,  // INT        [接受] 整數部分的數字
            S2,  // SIGN_ONLY  只讀過正負號
            S3,  // DOT_ONLY   讀過小數點，前後都沒有數字
            S4,  // FRAC       [接受] 小數部分的數字
            S5,  // EXP_START  剛讀過 e / E
            S6,  // EXP_SIGN   e 之後讀過正負號
            S7,  // EXP_INT    [接受] 指數部分的數字
        };
        // -1：陷阱狀態，碰到就 return false，表上不需要它的欄位

        // fsm[輸入][目前狀態] = 下一個狀態
        const int fsm[4][8] = {
            //  S0  S1  S2  S3  S4  S5  S6  S7
            {   S1, S1, S1, S4, S4, S7, S7, S7 },  // DIGIT
            {   S2, -1, -1, -1, -1, S6, -1, -1 },  // SIGN
            {   S3, S4, S3, -1, -1, -1, -1, -1 },  // DOT
            {   -1, S5, -1, -1, S5, -1, -1, -1 },  // EXP
        };

        // 字元 -> 輸入種類，也是一張表
        Input ch_map[256];
        fill(begin(ch_map), end(ch_map), INVALID);
        for (char c = '0'; c <= '9'; c++) ch_map[c] = DIGIT;
        ch_map['+'] = ch_map['-'] = SIGN;
        ch_map['.'] = DOT;
        ch_map['e'] = ch_map['E'] = EXP;

        int state = S0;
        for (char ch : s) {
            Input in = ch_map[(unsigned char)ch];
            if (in == INVALID) return false;
            state = fsm[in][state];
            if (state == -1) return false;
        }
        return state == S1 || state == S4 || state == S7;
    }
};

網路上的經典解法

總結一下

題目是一份文法，驗證它就是跑一個 DFA。圖照文法畫：integer、sign、decimal、exponent 四步；能停下來的是接受狀態，走不下去的進 DEAD。圖變成表，表搬進程式，主迴圈只剩查表。