英文原文
A valid number can be split up into these components (in order):
- A decimal number or an integer.
- (Optional) An
'e'
or'E'
, followed by an integer.
A decimal number can be split up into these components (in order):
- (Optional) A sign character (either
'+'
or'-'
). - One of the following formats:
- One or more digits, followed by a dot
'.'
. - One or more digits, followed by a dot
'.'
, followed by one or more digits. - A dot
'.'
, followed by one or more digits.
- One or more digits, followed by a dot
An integer can be split up into these components (in order):
- (Optional) A sign character (either
'+'
or'-'
). - One or more digits.
For example, all the following are valid numbers: ["2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789"]
, while the following are not valid numbers: ["abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53"]
.
Given a string s
, return true
if s
is a valid number.
Example 1:
Input: s = "0" Output: true
Example 2:
Input: s = "e" Output: false
Example 3:
Input: s = "." Output: false
Example 4:
Input: s = ".1" Output: true
Constraints:
1 <= s.length <= 20
s
consists of only English letters (both uppercase and lowercase), digits (0-9
), plus'+'
, minus'-'
, or dot'.'
.
中文题目
有效数字(按顺序)可以分成以下几个部分:
- 一个 小数 或者 整数
- (可选)一个
'e'
或'E'
,后面跟着一个 整数
小数(按顺序)可以分成以下几个部分:
- (可选)一个符号字符(
'+'
或'-'
) - 下述格式之一:
- 至少一位数字,后面跟着一个点
'.'
- 至少一位数字,后面跟着一个点
'.'
,后面再跟着至少一位数字 - 一个点
'.'
,后面跟着至少一位数字
- 至少一位数字,后面跟着一个点
整数(按顺序)可以分成以下几个部分:
- (可选)一个符号字符(
'+'
或'-'
) - 至少一位数字
部分有效数字列举如下:
["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 = "0" 输出:true
示例 2:
输入:s = "e" 输出:false
示例 3:
输入:s = "." 输出:false
示例 4:
输入:s = ".1" 输出:true
提示:
1 <= s.length <= 20
s
仅含英文字母(大写和小写),数字(0-9
),加号'+'
,减号'-'
,或者点'.'
。
通过代码
高赞题解
本题可以采用《编译原理》里面的确定的有限状态机(DFA)解决。构造一个DFA并实现,构造方法可以先写正则表达式,然后转为 DFA,也可以直接写,我就是直接写的,虽然大概率不会是最简结构(具体请参考《编译器原理》图灵出版社),不过不影响解题。DFA 作为确定的有限状态机,比 NFA 更加实用,因为对于每一个状态接收的下一个字符,DFA 能确定唯一一条转换路径,所以使用简单的表驱动的一些方法就可以实现,并且只需要读一遍输入流,比起 NFA 需要回读在速度上会有所提升。
构建出来的状态机如封面图片所示(红色为 终止状态,蓝色为 中间状态)。根据《编译原理》的解释,DFA 从状态 0 接受串 s 作为输入。当s耗尽的时候如果当前状态处于中间状态,则拒绝;如果到达终止状态,则接受。
然后,根据 DFA 列出如下的状态跳转表,之后我们就可以采用 表驱动法 进行编程实现了。需要注意的是,这里面多了一个状态 8,是用于处理串后面的若干个多余空格的。所以,所有的终止态都要跟上一个状态 8。其中,有一些状态标识为-1,是表示遇到了一些意外的字符,可以直接停止后续的计算。状态跳转表如下:
state | blank | +/- | 0-9 | . | e | other |
---|---|---|---|---|---|---|
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 |
状态图:
[]var isNumber = function(s) { let state = 0, finals = [0,0,0,1,0,1,1,0,1], transfer = [[ 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]], make = (c) => { switch(c) { case " ": return 0; case "+": case "-": return 1; case ".": return 3; case "e": return 4; default: let code = c.charCodeAt(); if(code >= 48 && code <= 57) { return 2; } else { return 5; } } }; for(let i=0; i < s.length; ++i) { state = transfer[state][make(s[i])]; if (state < 0) return false; } return finals[state]; };
[]class Solution { public int make(char c) { switch(c) { case ' ': return 0; case '+': case '-': return 1; case '.': return 3; case 'e': return 4; default: if(c >= 48 && c <= 57) return 2; } return -1; } public boolean isNumber(String s) { int state = 0; int finals = 0b101101000; int[][] transfer = new int[][]{{ 0, 1, 6, 2,-1}, {-1,-1, 6, 2,-1}, {-1,-1, 3,-1,-1}, { 8,-1, 3,-1, 4}, {-1, 7, 5,-1,-1}, { 8,-1, 5,-1,-1}, { 8,-1, 6, 3, 4}, {-1,-1, 5,-1,-1}, { 8,-1,-1,-1,-1}}; char[] ss = s.toCharArray(); for(int i=0; i < ss.length; ++i) { int id = make(ss[i]); if (id < 0) return false; state = transfer[state][id]; if (state < 0) return false; } return (finals & (1 << state)) > 0; } }
统计信息
通过次数 | 提交次数 | AC比率 |
---|---|---|
48185 | 177855 | 27.1% |
提交历史
提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
---|
相似题目
题目 | 难度 |
---|---|
字符串转换整数 (atoi) | 中等 |