请告诉我状态转换表是如何创建的，我尝试使用一些输入进行调试，但确实很难搞清楚。 以及为什么初始状态是状态1，状态3，5，8，9是最终状态。
代码如下:
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool isNumber(string s) {
static vector<unordered_map<string, int>> states = {
{}, // state 0
{{"blank", 1}, {"sign", 2}, {"digit", 3}, {"dot", 4}}, // state 1
{{"digit", 3}, {"dot", 4}}, // state 2
{{"digit", 3}, {"dot", 5}, {"e", 6}, {"blank", 9}}, // state 3, final
{{"digit", 5}}, // state 4
{{"digit", 5}, {"e", 6}, {"blank", 9}}, // state 5, final
{{"sign", 7}, {"digit",8}}, // state 6
{{"digit", 8}}, // state 7
{{"digit", 8}, {"blank", 9}}, // state 8, final
{{"blank", 9}} // state 9, final
};
int currState = 1;
string transition;
for(auto c : s) {
if(c>='0' && c<='9') transition = "digit";
else if(c=='-' || c=='+') transition = "sign";
else if(c == ' ') transition = "blank";
else if(c == '.') transition = "dot";
else if(c == 'e') transition = "e";
else return false;
auto it = states[currState].find(transition);
if (it == states[currState].end())
return false;
else
currState = it->second;
}
if (currState == 3 || currState == 5 || currState == 8 || currState == 9)
return true;
else
return false;
}
};
int main()
{
string str(" -90e3 ");
Solution sol;
bool ret = sol.isNumber(str);
return 0;
}
这个问题是一个相当复杂的DFA，但是有一些讨论帖子，解释了它是如何工作的，比如这个:
#include <string>
class Solution {
public:
bool isNumber(std::string number_string) {
while (!number_string.empty() && number_string[0] == ' ') {
number_string.erase(number_string.begin());
}
while (!number_string.empty() && number_string[number_string.size() - 1] == ' ') {
number_string.erase(number_string.end() - 1);
}
if (number_string.empty()) {
return false;
}
int state = 0;
for (int index = 0; index < number_string.size(); index++) {
if (number_string[index] == '+' || number_string[index] == '-') {
if (state == 0 || state == 3) {
state++;
} else {
return false;
}
} else if (number_string[index] == '.') {
if (state == 2) {
state = 7;
} else if (state == 0 || state == 1) {
state = 6;
} else {
return false;
}
} else if (number_string[index] >= '0' && number_string[index] <= '9') {
if (state == 1 || state == 4 || state == 6) {
state++;
} else if (state == 0 || state == 3) {
state += 2;
}
} else if (number_string[index] == 'e' || number_string[index] == 'E') {
if (state == 2 || state == 7) {
state = 3;
} else {
return false;
}
} else {
return false;
}
}
return (state == 2 || state == 5 || state == 7) ? true : false;
}
};
虽然，正则表达式并不是解决算法问题的最佳方法，但对于这个特定的问题，它本来是可以的。 例如，这将在Python中得到接受:
import re
class Solution:
def isNumber(self, s):
s = str(s).strip()
expression = r"^[+-]?(?:\d*\.\d+|\d+\.\d*|\d+)[Ee][+-]?\d+$|^[+-]?(?:\d*\.\d+|\d+\.\d*|\d+)$|^[+-]?\d+$"
match = re.match(expression, s)
return True if match else False
然而，由于某种原因，正则表达式在C++中给出了TLE。 请查看此帖子:
#include <regex>
regex r(R"(^(\s*)?[-+]?(((\d{1,})(\.\d{1,})?)|(\d{1,}\.)|(\.\d{1,}))(e[-+]?\d{1,})?(\s*)?$)");
class Solution {
public:
bool isNumber(const string& s) {
return regex_match(s, r);
}
};
在python中，这也可以简单地通过:
class Solution:
def isNumber(self, s):
try:
float(str(s).strip())
return True
except ValueError:
return False
在Java也是这样:
public class Solution {
public static final boolean isNumber(String s) {
s = s.trim();
boolean pointSeen = false;
boolean eSeen = false;
boolean digitSeen = false;
boolean digitAfterE = true;
for (int i = 0; i != s.length(); i++) {
if ('0' <= s.charAt(i) && s.charAt(i) <= '9') {
digitSeen = true;
digitAfterE = true;
} else if (s.charAt(i) == '.') {
if (eSeen || pointSeen) {
return false;
}
pointSeen = true;
} else if (s.charAt(i) == 'e') {
if (eSeen || ! digitSeen) {
return false;
}
digitAfterE = false;
eSeen = true;
} else if (s.charAt(i) == '-' || s.charAt(i) == '+') {
if (i != 0 && s.charAt(i - 1) != 'e') {
return false;
}
} else {
return false;
}
}
return digitSeen && digitAfterE;
}
}
