0065. Valid Number¶
题目信息¶
- 题号:
有效数字
- 难度:
Hard
- 主题:
字符串、语法解析、有限状态机
- 原题:
- 重点:
从分段匹配数字语法,推导到用有限见证变量完成一次扫描
题目重述¶
给定字符串 s,判断它是否完整表示一个合法十进制数。
底数可以是整数或小数,并允许一个可选的前导 + 或 -。合法小数必须至少包含一个数字,因此
"2."、".8" 和 "2.8" 都合法,单独的 "." 不合法。
底数后可以出现一个可选的指数部分。指数以 e 或 E 开始,后面可以有一个符号,并且必须包含至少
一个数字。指数只能是整数,不能包含小数点。
整个字符串都必须被上述语法消费,不能出现额外字符。约束为 1 <= s.length <= 20,字符只可能是
英文字母、数字、加号、减号或小数点。
自建示例¶
输入:s = "-.9e-2"
输出:true
底数 -.9 至少包含一个数字,指数 -2 是带符号整数。
输入:s = "46.e3"
输出:true
小数点前已有数字,所以 46. 是合法底数;指数 3 也完整。
输入:s = "1e+"
输出:false
指数符号后没有数字,指数部分未完成。
输入:s = "1.2.3"
输出:false
底数中只能出现一个小数点。
C++ 实现¶
#include <string>
class Solution {
private:
enum class State {
Start,
Sign,
Integer,
PointWithoutInteger,
PointAfterInteger,
Fraction,
Exponent,
ExponentSign,
ExponentInteger,
Invalid
};
bool isDigit(char ch) {
return ch >= '0' && ch <= '9';
}
bool isSign(char ch) {
return ch == '+' || ch == '-';
}
bool isExponent(char ch) {
return ch == 'e' || ch == 'E';
}
bool parseDigits(const std::string& s, int& index) {
const int start = index;
while (index < static_cast<int>(s.size()) && isDigit(s[index])) {
++index;
}
return index > start;
}
bool grammarParser(const std::string& s) {
int index = 0;
const int length = static_cast<int>(s.size());
if (index < length && isSign(s[index])) {
++index;
}
const bool integerDigits = parseDigits(s, index);
bool fractionDigits = false;
if (index < length && s[index] == '.') {
++index;
fractionDigits = parseDigits(s, index);
}
if (!integerDigits && !fractionDigits) {
return false;
}
if (index < length && isExponent(s[index])) {
++index;
if (index < length && isSign(s[index])) {
++index;
}
if (!parseDigits(s, index)) {
return false;
}
}
return index == length;
}
bool finiteStateMachine(const std::string& s) {
State state = State::Start;
for (char ch : s) {
const bool digit = isDigit(ch);
switch (state) {
case State::Start:
if (digit) {
state = State::Integer;
} else if (isSign(ch)) {
state = State::Sign;
} else if (ch == '.') {
state = State::PointWithoutInteger;
} else {
state = State::Invalid;
}
break;
case State::Sign:
if (digit) {
state = State::Integer;
} else if (ch == '.') {
state = State::PointWithoutInteger;
} else {
state = State::Invalid;
}
break;
case State::Integer:
if (digit) {
state = State::Integer;
} else if (ch == '.') {
state = State::PointAfterInteger;
} else if (isExponent(ch)) {
state = State::Exponent;
} else {
state = State::Invalid;
}
break;
case State::PointWithoutInteger:
state = digit ? State::Fraction : State::Invalid;
break;
case State::PointAfterInteger:
case State::Fraction:
if (digit) {
state = State::Fraction;
} else if (isExponent(ch)) {
state = State::Exponent;
} else {
state = State::Invalid;
}
break;
case State::Exponent:
if (digit) {
state = State::ExponentInteger;
} else if (isSign(ch)) {
state = State::ExponentSign;
} else {
state = State::Invalid;
}
break;
case State::ExponentSign:
case State::ExponentInteger:
state = digit ? State::ExponentInteger : State::Invalid;
break;
case State::Invalid:
return false;
}
if (state == State::Invalid) {
return false;
}
}
return state == State::Integer ||
state == State::PointAfterInteger ||
state == State::Fraction ||
state == State::ExponentInteger;
}
bool witnessScan(const std::string& s) {
bool seenDigit = false;
bool seenDot = false;
bool seenExponent = false;
bool digitAfterExponent = true;
for (int index = 0; index < static_cast<int>(s.size()); ++index) {
const char ch = s[index];
if (isDigit(ch)) {
seenDigit = true;
if (seenExponent) {
digitAfterExponent = true;
}
} else if (isSign(ch)) {
const bool atStart = index == 0;
const bool afterExponent =
index > 0 && isExponent(s[index - 1]);
if (!atStart && !afterExponent) {
return false;
}
} else if (ch == '.') {
if (seenDot || seenExponent) {
return false;
}
seenDot = true;
} else if (isExponent(ch)) {
if (seenExponent || !seenDigit) {
return false;
}
seenExponent = true;
digitAfterExponent = false;
} else {
return false;
}
}
return seenDigit && digitAfterExponent;
}
public:
bool isNumber(std::string s) {
return witnessScan(s);
}
};
题解¶
语法边界¶
直接调用浮点解析库并不能稳定表达题目语法。通用库可能接受空格、特殊值、十六进制格式或区域化写法,而本题 只允许十进制底数和可选指数。任务也只要求验证字符结构,不需要生成实际浮点值。
合法形式可以压缩为:
[sign] (digits [.] [digits] | . digits) [e/E [sign] digits]
底数必须至少出现一个数字。指数部分若存在,指数标记前必须已经形成合法底数,标记后必须形成一个完整整数。
分段解析¶
grammarParser 直接按照语法顺序消费字符串:
读取可选的底数符号;
读取小数点前的数字;
若出现小数点,再读取小数点后的数字;
确认小数点两侧至少一侧包含数字;
若出现指数标记,读取可选符号和至少一个指数数字;
确认索引最终恰好到达字符串末尾。
parseDigits 返回本次是否至少消费了一个数字。底数把点前和点后的两个结果合并,因此同时覆盖整数、普通
小数、前导点小数和尾随点小数。指数只接受 parseDigits 成功的结果,所以 "1e" 和 "1e+"
都会失败。
状态机展开¶
有限状态机把上述语法阶段显式列出。PointWithoutInteger 表示小数点前没有数字,此状态必须读取数字才能
继续;PointAfterInteger 表示小数点前已有数字,它本身已经是合法终态。
指数标记进入 Exponent 后,只能读取符号或数字。符号进入 ExponentSign,随后又必须读取数字才能
到达接受状态 ExponentInteger。因此未完成的符号和指数不会在字符串结束时被误判为合法。
接受状态只有四类:
Integer
PointAfterInteger
Fraction
ExponentInteger
它们分别对应整数、尾随点小数、含小数位的小数和带完整指数的数字。
见证变量压缩¶
状态机中的多个阶段可以压缩为四个布尔见证:
seenDigit:扫描前缀中已经出现数字;seenDot:底数已经出现小数点;seenExponent:已经进入指数部分;digitAfterExponent:指数出现后已经读到至少一个数字。
数字为底数或指数建立数字见证。小数点要求此前没有点且尚未进入指数。指数要求此前已有数字且尚未出现指数,
随后把 digitAfterExponent 重置为假。符号只允许位于字符串开头或紧跟指数标记。
扫描不变量¶
处理每个字符后,已扫描前缀若仍合法,就满足以下条件:
小数点至多一个,并且只属于底数;
指数标记至多一个,并且它之前已经出现数字;
每个符号都位于当前数字部分的起始位置;
若已经进入指数,
digitAfterExponent精确表示指数是否已经完整。
这些条件只依赖当前字符、前一个字符和四个累计见证,所以无需回溯。任一字符违反条件时可以立即返回
false。
状态演化¶
以 "-3.5E+2" 为例:
字符 |
状态变化 |
含义 |
|---|---|---|
|
位于下标 0 |
合法底数符号 |
|
|
底数已有数字 |
|
|
进入小数部分 |
|
数字见证保持 |
底数为 |
|
|
|
|
紧跟指数标记 |
合法指数符号 |
|
|
指数完整,最终接受 |
若字符串停在 E 或 E+,digitAfterExponent 会保持为假,最终检查便会拒绝这个未完成前缀。
方法关系¶
分段解析最接近文法定义,状态机最适合完整展示所有合法阶段,见证扫描则把等价阶段合并成最少状态。三种方法
都检查完整字符串,公开入口调用 witnessScan,因为它在保持语义清晰的同时只需一次线性扫描。
边界处理¶
"."和"+."没有任何数字,最终由seenDigit拒绝;".8"在点后建立数字见证,合法;"7."在点前已有数字,合法;"e9"在指数前没有数字,立即失败;"1e-"缺少指数数字,最终由digitAfterExponent拒绝;"1e2.3"在指数中出现小数点,由seenExponent拒绝;"--6"的第二个符号既不在开头也不跟随指数,立即失败。
复杂度分析¶
三种方法都只对长度为 n 的字符串进行常数遍扫描,时间复杂度为 O(n)。它们只维护固定数量的索引、
状态或布尔变量,额外空间复杂度为 O(1)。