Leetcode 150題目終結貼 - Valid Number

Validate if a given string is numeric.

Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true

Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.

2014-1-23 最後完成這道題目， Leetcode 150道題目正式完工

且每道題做了不下三遍。

貼出這道題是2014-3-7了。時隔一個月多了，期間又多做差不多兩遍，到現在才貼完，是因為到現在才算把所有題目都研究透徹了。每道題做了五遍以上了，打算以慢速繼續刷多幾遍，每天刷幾題吧。

算法修煉到現在差不多四個月了，期間過春節，沒什麼時間，算起來也有三個月。終於提高到了一個全新的境界了，對算法是信心滿滿的了。

有空全面地總結一下。

本博客也有所有Leetcode題的程序了，不太好的代碼都有更新了，所有Leetcode題目更新後的代碼可讀性都挺高的了。

本題5星級接近6星級的題目，本題是十分麻煩的題目，情況是非常多，網上也很多方法，其中最有效，優雅的方法是有限狀態自動機(Finite automata machine)。其他一般方法都會十分復雜，而代碼不能算優雅。為此我也曾經專門修了一個automata的知識。

只要設計好Finite Automata Machine之後，寫程序就可以很優雅，很簡單了。

但是，問題是要構造一個Finite Automata也是十分麻煩的事情，我畫了一張A4紙，像蜘蛛網一樣的，故此就不貼出來了，也搞了一兩個小時，要多練練automata才能快起來吧

注釋一下本題分多少狀態吧：

0初始無輸入或者只有space的狀態
1輸入了數字之後的狀態
2前面無數字，只輸入了Dot的狀態
3輸入了符號狀態
4前面有數字和有dot的狀態
5'e' or 'E'輸入後的狀態
6輸入e之後輸入Sign的狀態
7輸入e後輸入數字的狀態
8前面有有效數輸入之後，輸入space的狀態

共9種狀態了，難設計的是6,7,8狀態。

分好之後就好辦了，設計出根據輸入進行狀態轉換就OK了。

這裡的輸入可以分：

INVALID, // 0 Include: Alphas, '(', '&' ans so on
SPACE, // 1
SIGN, // 2 '+','-'
DIGIT, // 3 numbers
DOT, // 4 '.'
EXPONENT, // 5 'e' 'E'

然後就是畫蜘蛛網吧，什麼狀態可以轉換到什麼狀態的。

下面代碼也注釋出來了，參照了Leetcode論壇上的代碼寫的：

class Solution {
public:
	bool isNumber(const char *s) {
		enum InputType {
			INVALID,		// 0 Include: Alphas, '(', '&' ans so on
			SPACE,		// 1
			SIGN,		// 2 '+','-'
			DIGIT,		// 3 numbers
			DOT,			// 4 '.'
			EXPONENT,		// 5 'e' 'E'
		};
		int transTable[][6] = {
		//0INVA,1SPA,2SIG,3DI,4DO,5E
			-1,  0,  3,  1,  2, -1,//0初始無輸入或者只有space的狀態
			-1,  8, -1,  1,  4,  5,//1輸入了數字之後的狀態
			-1, -1, -1,  4, -1, -1,//2前面無數字，只輸入了Dot的狀態
			-1, -1, -1,  1,  2, -1,//3輸入了符號狀態
			-1,  8, -1,  4, -1,  5,//4前面有數字和有dot的狀態
			-1, -1,  6,  7, -1, -1,//5'e' or 'E'輸入後的狀態
			-1, -1, -1,  7, -1, -1,//6輸入e之後輸入Sign的狀態
			-1,  8, -1,  7, -1, -1,//7輸入e後輸入數字的狀態
			-1,  8, -1, -1, -1, -1,//8前面有有效數輸入之後，輸入space的狀態
		};
		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;
	}
};