状态图

停留在 6、3、5 状态时为有效数字。
image.png

解题步骤

  1. 构建一个表示状态的图
  2. 遍历字符串，并沿着图走，如果走到了某个节点无路可走就返回 false
  3. 遍历结束，如果走到 3/5/6，就返回 true，否则返回 false

通过图的方式实现

  • 时间复杂度：O (n)

  • 空间复杂度：O (1)

    1. function isNumber(s) {
    2.   const graph = {
    3.       0: { digit: 6, blank: 0, sign: 1, '.': 2 },
    4.       1: { digit: 6, '.': 2 },
    5.       2: { digit: 3 },
    6.       3: { digit: 3, e: 4, E: 4 },
    7.       4: { digit: 5, sign: 4 },
    8.       5: { digit: 5 },
    9.       6: { digit: 6, '.': 3, e: 4, E: 4 },
    10.       7: { digit: 5 },
    11.   };
    13.   let state = 0;
    15.   for (let c of s.trim()) {
    16.       if (c >= '0' && c <= '9') {
    17.           c = 'digit';
    18.       } else if (c === ' ') {
    19.           c = 'blank';
    20.       } else if (c === '+' || c === '-') {
    21.           c = 'sign';
    22.       }
    24.       state = graph[state][c];
    26.       if (state === undefined) {
    27.           return false;
    28.       }
    29.   }
    31.   if (state === 3 || state === 5 || state === 6) {
    32.       return true;
    33.   }
    35.   return false;
    36. }

代码中存在一个 for 循环，所以时间复杂度是 O (n) n 是字符串的长度。代码中虽然存在一个图数据结构，但是不会线性的增长，一直都是固定的大小，所以空间复杂度是 O (1)。