LeetCode 65. Valid Number：有限狀態自動機完整解析

問題描述

驗證給定字符串是否為合法數字。例子：

• "0" → true
• " 0.1 " → true
• "abc" → false
• "1 a" → false
• "2e10" → true

題目描述故意模糊，需自行總結所有規則再實現。

解法：確定有限狀態自動機 (DFA)

將字符分為 6 類輸入：

定義 9 個狀態：

• 0：初始/僅含空格
• 1：已讀數字
• 2：無前導數字，僅讀 .
• 3：已讀符號
• 4：已讀數字且含 .
• 5：已讀 e/E
• 6：e 後讀符號
• 7：e 後讀數字
• 8：合法數字後讀空格

狀態轉移表（-1 表示非法）：

// 輸入: INV SPA SIG DIG DOT EXP
int transTable[9][6] = {
    {-1,  0,  3,  1,  2, -1}, // 0
    {-1,  8, -1,  1,  4,  5}, // 1
    {-1, -1, -1,  4, -1, -1}, // 2
    {-1, -1, -1,  1,  2, -1}, // 3
    {-1,  8, -1,  4, -1,  5}, // 4
    {-1, -1,  6,  7, -1, -1}, // 5
    {-1, -1, -1,  7, -1, -1}, // 6
    {-1,  8, -1,  7, -1, -1}, // 7
    {-1,  8, -1, -1, -1, -1}  // 8
};

接受狀態：1, 4, 7, 8

C++ 實現

class Solution {
public:
    bool isNumber(const char *s) {
        enum InputType { INVALID, SPACE, SIGN, DIGIT, DOT, EXPONENT };
        int transTable[9][6] = {
            {-1, 0, 3, 1, 2, -1},
            {-1, 8, -1, 1, 4, 5},
            {-1, -1, -1, 4, -1, -1},
            {-1, -1, -1, 1, 2, -1},
            {-1, 8, -1, 4, -1, 5},
            {-1, -1, 6, 7, -1, -1},
            {-1, -1, -1, 7, -1, -1},
            {-1, 8, -1, 7, -1, -1},
            {-1, 8, -1, -1, -1, -1}
        };
        int state = 0;
        while (*s) {
            InputType input = INVALID;
            if (*s == ' ') input = SPACE;
            else if (*s == '+' || *s == '-') input = SIGN;
            else if (isdigit(*s)) input = DIGIT;
            else if (*s == '.') input = DOT;
            else if (*s == 'e' || *s == 'E') input = EXPONENT;
            state = transTable[state][input];
            if (state == -1) return false;
            ++s;
        }
        return state == 1 || state == 4 || state == 7 || state == 8;
    }
};

核心心得

• DFA 將複雜的字符串驗證轉化為清晰的狀態轉移，代碼極其簡潔健壯
• 狀態設計是關鍵：需覆蓋所有合法路徑，排除所有非法情況
• 表驅動法易於維護與擴展，避免巢狀 if-else 地獄