状态图
停留在 6、3、5 状态时为有效数字。
解题步骤
- 构建一个表示状态的图
- 遍历字符串,并沿着图走,如果走到了某个节点无路可走就返回 false
- 遍历结束,如果走到 3/5/6,就返回 true,否则返回 false
通过图的方式实现
- 时间复杂度:O (n)
空间复杂度:O (1)
function isNumber(s) {
const graph = {
0: { digit: 6, blank: 0, sign: 1, '.': 2 },
1: { digit: 6, '.': 2 },
2: { digit: 3 },
3: { digit: 3, e: 4, E: 4 },
4: { digit: 5, sign: 4 },
5: { digit: 5 },
6: { digit: 6, '.': 3, e: 4, E: 4 },
7: { digit: 5 },
};
let state = 0;
for (let c of s.trim()) {
if (c >= '0' && c <= '9') {
c = 'digit';
} else if (c === ' ') {
c = 'blank';
} else if (c === '+' || c === '-') {
c = 'sign';
}
state = graph[state][c];
if (state === undefined) {
return false;
}
}
if (state === 3 || state === 5 || state === 6) {
return true;
}
return false;
}
代码中存在一个 for 循环,所以时间复杂度是 O (n) n 是字符串的长度。代码中虽然存在一个图数据结构,但是不会线性的增长,一直都是固定的大小,所以空间复杂度是 O (1)。