Skip to main content

有效数字

题目​

有效数字(按顺序)可以分成以下几个部分:

  1. 一个 小数 或者 整数
  2. (可选)一个 'e' 或 'E', 后面跟着一个 整数

小数(按顺序)可以分成以下几个部分:

  1. (可选)一个符号字符('+' 或 '-')
  2. 下述格式之一:
    1. 至少一位数字, 后面跟着一个点 '.'
    2. 至少一位数字, 后面跟着一个点 '.', 后面再跟着至少一位数字
    3. 一个点 '.', 后面跟着至少一位数字

整数(按顺序)可以分成以下几个部分:

  1. (可选)一个符号字符('+' 或 '-')
  2. 至少一位数字

部分有效数字列举如下: ["2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789"]

部分无效数字列举如下: ["abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53"]

给你一个字符串 s, 如果 s 是一个 有效数字, 请返回 true.

提示:
  • 1 <= s.length <= 20
  • s 仅含英文字母(大写和小写), 数字(0 - 9), 加号 '+', 减号 '-', 或者点 '.'.
示例
输入: s = "0"
输出: true
输入: s = "e"
输出: false
输入: "."
输出: false

题解​

这道题的核心是有限状态机(deterministic finite automaton, DFA).

根据题意我们可以构造如下状态图(红色为终止状态, 蓝色为中间状态), 根据编译原理的解释, 有限状态机从状态 0 接受串 s 作为输入. 当 s 耗尽的时候如果当前状态处于中间状态, 则拒绝; 如果到达终止状态, 则接受. 因此可以得到一个 finals 数组, 具体看代码.

接下来根据状态流转编写 transfers 表:

65-is-number

statespace+/-0-9.e/Eillegal
0
(开头的空格)		0
(后面可以再跟一个开头的空格)		1
(后面可以跟一个正负符号)		6
(后面可以跟一个小数点前的数字)		2
(后面可以跟一个小数点)		-1
(后面不可以跟指数符号)		-1
(后面不可以跟非法字符)
1
(正负符号)		-1
(后面不可以跟一个空格)		-1
(后面不可以跟一个正负符号)		6
(后面可以跟一个小数点前的数字)		2
(后面可以跟一个小数点)		-1
(后面不可以跟指数符号)		-1
(后面不可以跟非法字符)
2
(小数点)		-1
(后面不可以跟一个空格)		-1
(后面不可以跟一个正负符号)		3
(后面可以跟一个小数点后的数字)		-1
(后面不可以跟一个小数点)		-1
(后面不可以跟指数符号)		-1
(后面不可以跟非法字符)
3
(小数点后的数字)		8
(后面可以跟一个结尾的空格)		-1
(后面不可以跟一个正负符号)		3
(后面可以跟一个小数点后的数字)		-1
(后面不可以跟一个小数点)		4
(后面可以跟一个指数符号)		-1
(后面不可以跟非法字符)
4
(指数符号)		-1
(后面不可以跟一个空格)		7
(后面可以跟一个指数符号后的正负符号)		5
(后面可以跟一个指数符号后的数字)		-1
(后面不可以跟一个小数点)		-1
(后面不可以跟指数符号)		-1
(后面不可以跟非法字符)
5
(指数符号后的数字)		8
(后面可以跟一个结尾的空格)		-1
(后面不可以跟一个正负符号)		5
(后面可以跟一个指数符号后的数字)		-1
(后面不可以跟一个小数点)		-1
(后面不可以跟指数符号)		-1
(后面不可以跟非法字符)
6
(小数点前的数字)		8
(后面可以跟一个结尾的空格)		-1
(后面不可以跟一个正负符号)		6
(后面可以跟一个小数点前的数字)		3
(后面可以跟一个小数点后的数字)		4
(后面可以跟一个指数符号)		-1
(后面不可以跟非法字符)
7
(指数符号后的正负符号)		-1
(后面不可以跟一个空格)		-1
(后面不可以跟一个正负符号)		5
(后面可以跟一个指数符号后的数字)		-1
(后面不可以跟一个小数点)		-1
(后面不可以跟指数符号)		-1
(后面不可以跟非法字符)
8
(结尾的空格)		8
(后面可以跟一个结尾的空格)		-1
(后面不可以跟一个正负符号)		-1
(后面不可以跟一个数字)		-1
(后面不可以跟一个小数点)		-1
(后面不可以跟指数符号)		-1
(后面不可以跟非法字符)
/**
 * @param {string} s
 * @return {boolean}
 */
var isNumber = function (s) {
  let state = 0
  const n = s.length
  const finals = [false, false, false, true, false, true, true, false, true]
  const transfers = [
    [0, 1, 6, 2, -1, -1],
    [-1, -1, 6, 2, -1, -1],
    [-1, -1, 3, -1, -1, -1],
    [8, -1, 3, -1, 4, -1],
    [-1, 7, 5, -1, -1, -1],
    [8, -1, 5, -1, -1, -1],
    [8, -1, 6, 3, 4, -1],
    [-1, -1, 5, -1, -1, -1],
    [8, -1, -1, -1, -1, -1],
  ]

  const make = (ch) => {
    if (/[0-9]/.test(ch)) return 2

    switch (ch) {
      case ' ':
        return 0
      case '+':
      case '-':
        return 1
      case '.':
        return 3
      case 'e':
      case 'E':
        return 4
      default:
        return 5
    }
  }

  for (const ch of s) {
    state = transfers[state][make(ch)]

    // 如果遇到非法状态, 提前终止
    if (state < 0) return false
  }

  // 如果遍历完后能成功到达终止状态, 说明是一个合法数字, 否则失败
  return finals[state]
}