[LeetCode]Valid Number

题目链接

这道题首先要明确requirement，举足够多的例子确定cover所有的edge cases，比如：

• 普通的整数和小数都是valid的，比如9和0.3
• 9. 和 .3也都是valid的，但是只有一个.肯定不是valid的
• 科学计数法的情况下，前半部分允许出现整数或者小数，后半部分只允许整数
• 9e3, -5.4e-6都是valid的
• 5e3.4不是valid的
• e只允许最多出现一次。+/-在e之前只允许最多出现一次，在e之后同样最多出现一次，并且只能在树的最前端
• 我们允许所有的leading和trailing zeros，比如000009和00000.30000都是合法的
• 我们允许所有的leading和trailing whitespaces，但是不允许中间的whitespaces

这些情况都要考虑的话，写出来的代码一定是十分繁杂的，并且很有可能会遗漏，非常不这么推荐这么写。这道题最简单的方式使用regex，如下所示：

• ^(-|\+)?(\d+\.?\d*|\.\d+)(e(-|\+)?\d+)?$

乍看之下有点复杂，但是break down之后思路是很清晰的：

1. ^和$代表从头到尾match input string，代表整个input string需要match这个regex pattern，只有substring是不行的
2. (-|\+)?代表match正负号一次或者零次
3. (\d+\.?\d*|\.\d+)
1. 第一部分\d+\.?\d*，\d+代表整数部分，\.?代表零次或者一次小数点，\d*代表零次或者多次数字。也就是说 5, 7.83, 23. 这样的都可以match
2. 第二部分\.\d+，代表match没有整数部分的小数，比如.3434
4. (e(-|\+)?\d+)?, 这一部分代表科学计数法的部分，总的来说就是一次e后面接整数。最后的?代表整体出现一次或者零次
1. e代表match e一次
2. (-|\+)? 同上，match正负号一次或者零次
3. \d+，match所有整数

所以整个regex是可以cover所有情况的，有兴趣的可以去regex101去试一试。

虽然我们可以用regex解，但这肯定不是expected的解法。regex归根到底也是状态的转移，我们可以用DFA来模拟。我们可以根据以上情况建状态机，基本思路是先建立整数的部分，然后小数的部分，最后科学计数法的部分，状态机如下图所示：

图一

我们可以看出只有最后停在2, 4, 7的状态才是合法的状态。

对于所有的输入来说，我们同样可以给他们标号：

• +/-记为0
• 0-9记为1
• . 记为2
• e记为3
• 其余记为4

注意我们这里不管whitespace，我们只需要trim掉所有的leading和trailing zeroes，剩下的whitespace都是不合法的，我们全部归到4即可。那么我们就可以画出transfer table，如下图所示，行代表状态，列代表输入：

那么我们根据这张表和输入的字符每次进行状态转移即可。-1代表非法的状态，如果我们到达了非法的状态，或者结束的时候没有停在合法的状态(2, 4, 7)，就说明输入string不合法。否则合法。时间复杂度O(N)，N为输入字符串的长度。代码如下：

	class Solution {
	public:
	bool isNumber(string s) {
	vector<vector<int>> transferTable = {
	{1, 2, 3, -1, -1},
	{-1, 2, 3, -1, -1},
	{-1, 2, 4, 5, -1},
	{-1, 4, -1, -1, -1},
	{-1, 4, -1, 5, -1},
	{6, 7, -1, -1, -1},
	{-1, 7, -1, -1, -1},
	{-1, 7, -1, -1, -1}
	};
	int state = 0, len = s.size(), i = 0, j = len - 1;
	while(i < len && s[i] == ' ')++i;
	while(j >= 0 && s[j] == ' ')--j;
	if(j < i)return false;
	for(int k = i; k <= j; ++k)
	{
	int input = getInput(s[k]);
	state = transferTable[state][input];
	if(state == -1)return false;
	}
	return state == 2 || state == 4 || state == 7;
	}
	private:
	int getInput(char c)
	{
	switch(c)
	{
	case '+':
	case '-':
	return 0;
	case '0':
	case '1':
	case '2':
	case '3':
	case '4':
	case '5':
	case '6':
	case '7':
	case '8':
	case '9':
	return 1;
	case '.':
	return 2;
	case 'e':
	return 3;
	default:
	return 4;
	}
	}
	};

view raw Valid Number.cpp hosted with ❤ by GitHub