剑指Offer题解 - Day58
剑指 Offer 20. 表示数值的字符串
请实现一个函数用来判断字符串是否表示「数值」（包括整数和小数）。
「数值」（按顺序）可以分成以下几个部分：
- 若干空格
- 一个 「小数」 或者 「整数」
- （可选）一个
'e'或'E'，后面跟着一个 「整数」 - 若干空格
「小数」（按顺序）可以分成以下几个部分：
- （可选）一个符号字符（'+' 或 '-'）
- 下述格式之一：
- 至少一位数字，后面跟着一个点 '.'
- 至少一位数字，后面跟着一个点 '.' ，后面再跟着至少一位数字
- 一个点 '.' ，后面跟着至少一位数字
「整数」（按顺序）可以分成以下几个部分：
- （可选）一个符号字符（'+' 或 '-'）
- 至少一位数字
部分数值列举如下：
["+100", "5e2", "-123", "3.1416", "-1E-16", "0123"]
部分非数值列举如下：
["12e", "1a3.14", "1.2.3", "+-5", "12e+5.4"]
示例 1：
输入：s = "e"
输出：false
示例 2：
输入：s = "."
输出：false
示例 3：
输入：s = " .1 "
输出：true
提示：
1 <= s.length <= 20- s 仅含英文字母（大写和小写），数字（0-9），加号 '+' ，减号 '-' ，空格 ' ' 或者点 '.' 。
思路：
首先考虑使用正则匹配进行题解。
合法的字符包括：空格 「 」、数字「 0-9 」 、正负号 「 +、− 」 、小数点 「 . 」 、幂符号 「 e、E」
正则
/**
* @param {string} s
* @return {boolean}
*/
var isNumber = function(s) {
if (typeof s !== 'string') {
return false;
}
return /^ *[\+\-]?((\d+|\.\d+|\d+\.\d+)(\.?(e|E)[\+\-]?\d+)?|\d+\.((e|E)[\+\-]?\d+)?) *$/.test(s)
};
正则可以通过提交，但是正则很容易产生性能问题，所以正则不是最优解。
状态机
本机可以使用 「有限状态自动机」 解决。题解参考自这里[1]。
按照字符串从左到右的顺序，定义以下 9 种状态。
- 开始的空格
- 幂符号前的正负号
- 小数点前的数字
- 小数点、小数点后的数字
- 当小数点前为空格时，小数点、小数点后的数字
- 幂符号
- 幂符号后的正负号
- 幂符号后的数字
- 结尾的空格
其中，合法的结束状态有 2, 3, 7, 8 。
首先，需要设置状态转移表。按照上面分析的5种合法字符，分别使用以下缩写来表示：
- ' ' → 空格 「 」
- 'd' → 数字「 0-9 」
- 's' → 正负号 「 +、− 」
- '.' → 小数点 「 . 」
- 'e' → 幂符号 「 e、E」
设 states[i] ，其中 i 为所处状态， states[i] 使用哈希表存储可转移至的状态。键值对 (key, value) 含义：输入字符 key ，则从状态 i 转移至状态 value 。
初始化的状态值记为0。然后进行状态转移循环。
记录字符类型 t ：分为四种情况。
- 当 c 为正负号时，执行 t = 's' ;
- 当 c 为数字时，执行 t = 'd' ;
- 当 c 为 e 或 E 时，执行 t = 'e' ;
- 当 c 为 . 或 空格 时，执行 t = c （即用字符本身表示字符类型）;
- 否则，执行 t = '?' ，代表为不属于判断范围的非法字符，后续直接返回 false 。
「终止条件」：若字符类型 t 不在哈希表 states[p] 中，说明无法转移至下一状态，因此直接返回 falsefalse 。「状态转移」：状态 p 转移至 states[p][t] 。
循环结束后， 如果状态属于2，3，7，8，则意味着合法，返回true；否则返回false。
/**
* @param {string} s
* @return {boolean}
*/
var isNumber = function(s) {
const states = new Map([
[0, new Map([
[' ', 0],
['s', 1],
['d', 2],
['.', 4],
])],
[1, new Map([
['d', 2],
['.', 4],
])],
[2, new Map([
['d', 2],
['.', 3],
['e', 5],
[' ', 8],
])],
[3, new Map([
['d', 3],
['e', 5],
[' ', 8],
])],
[4, new Map([
['d', 3]
])],
[5, new Map([
['s', 6],
['d', 7]
])],
[6, new Map([
['d', 7]
])],
[7, new Map([
['d', 7],
[' ', 8],
])],
[8, new Map([
[' ', 8]
])]
])
let p = 0;
let t = null;
for (const c of s) {
if(c >= '0' && c <= '9') t = 'd';
else if(c === '+' || c === '-') t = 's';
else if(c === 'e' || c === 'E') t = 'e';
else if(c === '.' || c === ' ') t = c;
else t = '?';
if (!states.get(p).has(t)) return false;
p = states.get(p).get(t);
}
return p === 2 || p === 3 || p === 7 || p === 8;
};
- 时间复杂度 O(n)。
- 空间复杂度 O(1)。
分析：
有限状态机的难点在于状态转移表。我们通过Map来存储，只要最终状态属于2、3、7、8，我们就认为是合法数值字符串。
总结
本题考查合法数值字符串的判断。最优解是使用有限状态机解决。但是状态转移不容易想到，难度系数中等。
参考资料
[1]
这里: https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/5dkal2/
腾讯云开发者
