leetcode 第65題 有效數字

題目

有效數字（按順序）可以分成以下幾個部分：

1. 一個 小數 或者 整數
2. （可選）一個 ‘e’ 或 ‘E’ ，後面跟着一個 整數

小數（按順序）可以分成以下幾個部分：

1. （可選）一個符号字元（’+’ 或 ‘-’）
2. 下述格式之一：
   1. 至少一位數字，後面跟着一個點 ‘.’
   2. 至少一位數字，後面跟着一個點 ‘.’ ，後面再跟着至少一位數字
   3. 一個點 ‘.’ ，後面跟着至少一位數字

整數（按順序）可以分成以下幾個部分：

1. （可選）一個符号字元（’+’ 或 ‘-’）
2. 至少一位數字

部分有效數字列舉如下：

[“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”]

給你一個字元串 s ，如果 s 是一個 有效數字 ，請傳回 true 。

思路

這個題的方法有三種：正規表達式、狀态機、分類讨論。

1、正規表達式的思路很明顯，不細說。可以參考解法

2、狀态機其實是比較有意思且規範的一個解法，具體思路可以直接參考官方解法。其實難點就在于完整梳理整個過程中的所有狀态，保證不重不漏。然後根據狀态機進行程式設計和狀态轉移，如果在狀态轉移過程中出現無效轉移、或者最後的狀态不是一種結束狀态，那麼就認為輸入條件是不符合狀态機規範的。

3、至于分類讨論，其實就是直接分析有效數字存在的規律，然後直接進行拆解。可以參考此解法，先按e進行拆分，然後左右兩側分别判斷是否是有效數字。這裡邊還需要考慮e和小數點隻能出現一次，是以該解法還是需要考慮比較多的細節，不過實作代碼寫的很精簡。

複雜度

時間複雜度很明顯是O(n)， 空間複雜度是O(1)

代碼就不貼了，上面連結都有詳細代碼。

總結

這種用有限狀态自動機（DFA）實作的題目之前沒見過，很有意思，記錄一下。

另外，看到資料說：正規表達式的實作基礎也是DFA，可以擴充了解一下。