# 65 - Valid Number

解法一 - 將各階段分類好漸進處理

這種題目最麻煩的地方就在於，如果沒有把規則想好，就會涵蓋不到一些 edge cases，進而為了處理這些奇怪 case 使得邏輯變得很混亂。

第一步，我們可以先想想合理的 case 應該要長什麼樣子，先寫出第一版的 valid pattern（[] 裡面表示是 optional，概念就像 linux command line tool 的說明）：

[+/-] 數字(可以是小數) [e數字(不能是小數)]

而不屬於這個 valid pattern 的其他字串都視為 invalid。

接下來我們可以用題目中提供的 test cases 檢視一下我們的 pattern 是否已經足夠，會發現有幾個例子沒有被涵蓋到：

• " 0.1 " => true (最前面跟最後面都可以有 space)

• " 6e-1" => true (e 後面的數字可以有 +/-)

[spaces][+/-]數字(可以是小數)[e[+/-]數字(不能是小數)][spaces]

所以我們的邏輯應該要依序處理：

1. Skip spaces

2. Check '+'/'-'

3. Check digital(can contain ".")

4. Check exponent a. Check '+'/'-' b. Check digital(cannot contain ".")

5. Check space

class Solution {
public:
    bool isNumber(string s) 
    {
        int i=0;

        // Skip the spaces
        for(; s[i] == ' '; i++) {}

        // Check for '+'/'-'
        if(s[i] == '+' || s[i] == '-') i++;

        // Check digital
        int num, pt;
        for(num=0, pt=0; (s[i]<='9' && s[i]>='0') || s[i]=='.'; i++)
            s[i] == '.' ? pt++ : num++;       
        if(pt>1 || num<1) // no more than one point, at least one digit
            return false;

        // Check exponent
        if(s[i] == 'e') {
            i++;

            // Check '+'/'-'
            if(s[i] == '+' || s[i] == '-') i++;

            // Check digital(cannot contain ".")
            for(num=0; (s[i]<='9' && s[i]>='0'); i++, num++) {}
            if(num<1) // at least one digit
                return false;
        }

        // Skip spaces
        for(; s[i] == ' '; i++) {}

        // must reach the end of string
        return s[i]=='\0';
    }
};

解法二 - Deterministic Finite Automaton

這個解法太帥了，先記錄一下有用的討論串：

1. https://leetcode.com/problems/valid-number/discuss/23798/Cleanest-C%2B%2B-Solution-using-DFA-(impress-your-interviewer-with-elegant-code!!)

2. https://leetcode.com/problems/valid-number/discuss/23725/C%2B%2B-My-thought-with-DFA

解法三 - Regular Expression

在解法一寫出合理 pattern 的時候，我就想到了 regular expression，不過 regular expression 的寫法我已經忘了，貼一個相關的 討論串 跟 影片-Regular Expressions (Regex) Tutorial: How to Match Any Pattern of Text：

class Solution {
public:
    bool isNumber(string s) {
        //[spaces][+/-]數字(可以是小數)[e[+/-]數字(不能是小數)][spaces]
        //regex pattern("\\s*[+-]?(([0-9]*\.?[0-9]+)|([0-9]+\.?[0-9]*))([e][+-]?[0-9]+)?\\s*");
        regex pattern("\s*[+-]?(([0-9]*\.?[0-9]+)|([0-9]+\.?[0-9]*))([e][+-]?[0-9]+)?\s*");

        return regex_match(s, pattern); 
    }
};

這個版本無法通過 leetcode 上的 test cases，不過我用 Sublime Text 測試時結果正確，不確定是什麼問題，先擱著。