思路
方法一:常规解法
只检查每个字符后面的字符,需要判断的地方有:
1. 消去字符串的前置空格和后置空格,比如“1 ”是合法的
2. 正负号:
(1) 只能出现在第1个字符,或者出现在e或E的后1个字符;
(2) 正负号的后面一个字符必须是数字, 或者小数点
(3) 最多只有2个正负号
3. 指数e和E:
(1) 只能出现1次
(2) 前面那个字符必须是数字或者小数点,如果是小数点则此小数点不能在开头位置。
比如.e3就是非法的,"46.e3"是合法的
(3) 后面那个字符必须是数字或者正负号
(4) 后面的所有字符都不能出现小数点,这一点可以在小数点的第(3)个判断点再进行判断
4. 小数点:
(2) 不能出现在e或E后面的任何位置
(3) 出现在结尾,前面那个字符必须是数字。比如123.是合法的
5. 前置0:可以存在任意个前置0
1 class Solution {
2 private:
3 int ePos = -1; //E或e的位置(下标)
4 int plusMinusSignNum = 0; //正负号的个数
5 int pointPos = -1; //小数点的位置
6
7 public:
8 bool isNumber(string s) {
9
10 /*1. 消去字符串前置空格和后置空格*/
11 if(s.empty())
12 return false;
13
14 int start = 0, end = s.length()-1;
15 for(int i = 0; i < s.length(); ++i) {
16 if(s[i] == ' ')
17 start++;
18 else
19 break;
20 }
21
22 if(start == s.length())
23 return false;
24
25 for(int i = s.length()-1; i >= 0; --i) {
26 if(s[i] == ' ')
27 end--;
28 else
29 break;
30 }
31
32 string s2(end-start+1, ' ');
33 copy(s.begin()+start, s.begin()+end+1, s2.begin());
34 s = string(s2.begin(), s2.end());
35
36 for(int i = 0; i < s.length(); ++i) {
37 if(s[i] == '+' || s[i] == '-') {
38 /*2. 检查正负号*/
39 //(1)只能出现在第1个字符,或者出现在e或E的后1个字符;
40 if(i != ePos+1)
41 return false;
42 //(2)正负号的后面一个字符必须是数字, 或者小数点
43 if(i+1 <= s.length()-1) {
44 if(!( (s[i+1] >= '0' && s[i+1] <= '9') || s[i+1] == '.' ))
45 return false;
46 } else {
47 //后面无字符,直接返回false
48 return false;
49 }
50
51 plusMinusSignNum++;
52 //(3)最多只有2个正负号
53 if(plusMinusSignNum > 2)
54 return false;
55
56 } else if(s[i] == 'e' || s[i] == 'E') {
57 /*3. 检查E或e*/
58 //(1)只能出现1次
59 if(ePos != -1)
60 return false;
61
62 ePos = i;
63
64 if(i-1 >= 0) {
65 //(2)前面那个字符必须是数字或者小数点,如果是小数点则此小数点不能在开头位置
66 if(!( ( s[i-1] >= '0' && s[i-1] <= '9') || (s[i-1] == '.' && i-1 != 0)) )
67 return false;
68 } else {
69 //前面无字符,直接返回false
70 return false;
71 }
72
73 //(3)后面那个字符必须是数字或者正负号
74 if(i+1 <= s.length()-1) {
75 if(!( (s[i+1] >= '0' && s[i+1] <= '9') || s[i+1] == '+' || s[i+1] == '-' ))
76 return false;
77 } else {
78 //后面无字符,直接返回false
79 return false;
80 }
81
82 } else if(s[i] == '.') {
83 /*4. 检查小数点*/
84
85 //(1)只能出现1次
86 if(pointPos != -1)
87 return false;
88
89 pointPos = i;
90
91 //(2)不能出现在e或E后面的任何位置
92 if(pointPos > ePos && ePos != -1)
93 return false;
94
95 //(3)出现在结尾,前面那个字符必须是数字
96 if(i == s.length()-1) {
97 if(i-1 >= 0) {
98 if(s[i-1] < '0' || s[i-1] > '9')
99 return false;
100 } else {
101 return false;
102 }
103
104 }
105
106 } else {
107 //其他符号中,如果有非数字符号
108 if(s[i] < '0' || s[i] > '9')
109 return false;
110 }
111 }
112
113 return true;
114
115 }
116 };
方法二:有限状态自动机
本解法来自:面试题20. 表示数值的字符串(有限状态自动机,清晰图解)
C++实现
1 class Solution {
2 private:
3 /*有限状态自动机DFA*/
4 unordered_map<char, int> states[9] = {
5 unordered_map<char, int>({{' ', 0}, {'s', 1}, {'d', 2}, {'.', 4}}), // 0.
6 unordered_map<char, int>({{'d', 2}, {'.', 4}}), // 1.
7 unordered_map<char, int>({{'d', 2}, {'.', 3}, {'e', 5}, {' ', 8}}), // 2.
8 unordered_map<char, int>({{'d', 3}, {'e', 5}, {' ', 8}}), // 3.
9 unordered_map<char, int>({{'d', 3}}), // 4.
10 unordered_map<char, int>({{'s', 6}, {'d', 7}}), // 5.
11 unordered_map<char, int>({{'d', 7}}), // 6.
12 unordered_map<char, int>({{'d', 7}, {' ', 8}}), // 7.
13 unordered_map<char, int>({{' ', 8}}) // 8.
14 };
15
16 public:
17 bool isNumber(string s) {
18 int p = 0;
19 char t;
20 for(char c : s) {
21 if(c >= '0' && c <= '9') t = 'd';
22 else if(c == '+' || c == '-') t = 's';
23 else if(c == 'e' || c == 'E') t = 'e';
24 else if(c == '.' || c == ' ') t = c;
25 else t = '?';
26 if(states[p].count(t) == 0)
27 return false;
28 p = (int)states[p][t];
29 }
30 return p == 2 || p == 3 || p == 7 || p == 8;
31 }
32 };
Java实现
1 class Solution {
2 public boolean isNumber(String s) {
3 Map[] states = {
4 new HashMap<>() {{ put(' ', 0); put('s', 1); put('d', 2); put('.', 4); }}, // 0.
5 new HashMap<>() {{ put('d', 2); put('.', 4); }}, // 1.
6 new HashMap<>() {{ put('d', 2); put('.', 3); put('e', 5); put(' ', 8); }}, // 2.
7 new HashMap<>() {{ put('d', 3); put('e', 5); put(' ', 8); }}, // 3.
8 new HashMap<>() {{ put('d', 3); }}, // 4.
9 new HashMap<>() {{ put('s', 6); put('d', 7); }}, // 5.
10 new HashMap<>() {{ put('d', 7); }}, // 6.
11 new HashMap<>() {{ put('d', 7); put(' ', 8); }}, // 7.
12 new HashMap<>() {{ put(' ', 8); }} // 8.
13 };
14 int p = 0;
15 char t;
16 for(char c : s.toCharArray()) {
17 if(c >= '0' && c <= '9') t = 'd';
18 else if(c == '+' || c == '-') t = 's';
19 else if(c == 'e' || c == 'E') t = 'e';
20 else if(c == '.' || c == ' ') t = c;
21 else t = '?';
22 if(!states[p].containsKey(t)) return false;
23 p = (int)states[p].get(t);
24 }
25 return p == 2 || p == 3 || p == 7 || p == 8;
26 }
27 }