1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class Solution {
public boolean isNumber(String s) {
boolean seenDigit = false;
boolean seenDot = false;
boolean seenExp = false;
char[] sArray = s.toCharArray();
for (int i = 0; i < sArray.length; i++) {
if (Character.isDigit(sArray[i])) {
seenDigit = true;
} else if (sArray[i] == '+' || sArray[i] == '-') {
if (i > 0 && sArray[i - 1] != 'e' && sArray[i - 1] != 'E') {
return false;
}
} else if (sArray[i] == '.') {
if (seenDot || seenExp) {
return false;
}
seenDot = true;
} else if (sArray[i] == 'e' || sArray[i] == 'E') {
if (seenExp || !seenDigit) {
return false;
}
seenExp = true;
seenDigit = false;
} else {
return false;
}
}
return seenDigit;
}
}
|
一共有四种: digit, dot, sign和exp.
sign只能在开头以及e的后面出现.
dot只能在前面没有dot并且前面没有e的位置出现. dot后可以没有digit.
digit可以在任意位置出现.
exp只能在之前没有exp出现而且之前必须有digit. e后面也需要有digit.
时间复杂度: O(n)
空间复杂度: O(1)
DFA每个node就是一个状态, 从当前状态可以到别的状态. 根据题意, 当下是digit的时候, 下一个可以是digit, dot, exp都可以,
但是不能是sign, 因此发散出三条线去到三个不同的其他状态. 当前是dot, 下一个只能是digit. 这样我们就知道发散出去的线路有哪些.
至于状态, 就是看上面的那三个boolean的组合有哪些.
时间复杂度和空间复杂度不变.
