LeetCode 65: Valid Number (Deterministic State Parsing)
LeetCode 65StringFinite State MachineToday we solve LeetCode 65 - Valid Number.
Source: https://leetcode.com/problems/valid-number/
English
Problem Summary
Given a string s, return whether it is a valid decimal number. Valid forms include integer, decimal, and scientific notation (e/E with exponent).
Key Insight
This is a grammar-checking problem. A deterministic state scan is reliable: track whether we have seen digit, dot, exponent, and whether exponent has digits.
Brute Force and Limitations
Trying many ad-hoc string splits can miss edge cases like ".1", "3.", "-90E3", or accidentally accept invalid forms like "1e" and "e3".
Optimal Algorithm Steps (Single Pass State Rules)
1) Trim leading/trailing spaces.
2) Scan each character with four flags: seenDigit, seenDot, seenExp, digitAfterExp.
3) Digit: set seenDigit=true; if after exponent, set digitAfterExp=true.
4) Dot: valid only before exponent and only once.
5) e/E: valid only once and only after at least one digit; then require digits after it.
6) Sign +/-: valid only at beginning or right after e/E.
7) Any other char => invalid. Final answer needs seenDigit && digitAfterExp.
Complexity Analysis
Time: O(n).
Space: O(1).
Common Pitfalls
- Forgetting to require digits after exponent ("1e" should be false).
- Allowing sign in the middle without exponent context.
- Allowing a second dot or dot after exponent.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public boolean isNumber(String s) {
s = s.trim();
if (s.isEmpty()) return false;
boolean seenDigit = false;
boolean seenDot = false;
boolean seenExp = false;
boolean digitAfterExp = true;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (Character.isDigit(c)) {
seenDigit = true;
if (seenExp) digitAfterExp = true;
} else if (c == '+' || c == '-') {
if (i != 0 && s.charAt(i - 1) != 'e' && s.charAt(i - 1) != 'E') return false;
} else if (c == '.') {
if (seenDot || seenExp) return false;
seenDot = true;
} else if (c == 'e' || c == 'E') {
if (seenExp || !seenDigit) return false;
seenExp = true;
digitAfterExp = false;
} else {
return false;
}
}
return seenDigit && digitAfterExp;
}
}func isNumber(s string) bool {
s = strings.TrimSpace(s)
if len(s) == 0 {
return false
}
seenDigit, seenDot, seenExp := false, false, false
digitAfterExp := true
for i := 0; i < len(s); i++ {
c := s[i]
if c >= '0' && c <= '9' {
seenDigit = true
if seenExp {
digitAfterExp = true
}
} else if c == '+' || c == '-' {
if i != 0 && s[i-1] != 'e' && s[i-1] != 'E' {
return false
}
} else if c == '.' {
if seenDot || seenExp {
return false
}
seenDot = true
} else if c == 'e' || c == 'E' {
if seenExp || !seenDigit {
return false
}
seenExp = true
digitAfterExp = false
} else {
return false
}
}
return seenDigit && digitAfterExp
}class Solution {
public:
bool isNumber(string s) {
int l = 0, r = (int)s.size() - 1;
while (l <= r && isspace((unsigned char)s[l])) l++;
while (r >= l && isspace((unsigned char)s[r])) r--;
if (l > r) return false;
bool seenDigit = false, seenDot = false, seenExp = false, digitAfterExp = true;
for (int i = l; i <= r; i++) {
char c = s[i];
if (isdigit((unsigned char)c)) {
seenDigit = true;
if (seenExp) digitAfterExp = true;
} else if (c == '+' || c == '-') {
if (i != l && s[i - 1] != 'e' && s[i - 1] != 'E') return false;
} else if (c == '.') {
if (seenDot || seenExp) return false;
seenDot = true;
} else if (c == 'e' || c == 'E') {
if (seenExp || !seenDigit) return false;
seenExp = true;
digitAfterExp = false;
} else {
return false;
}
}
return seenDigit && digitAfterExp;
}
};class Solution:
def isNumber(self, s: str) -> bool:
s = s.strip()
if not s:
return False
seen_digit = False
seen_dot = False
seen_exp = False
digit_after_exp = True
for i, ch in enumerate(s):
if ch.isdigit():
seen_digit = True
if seen_exp:
digit_after_exp = True
elif ch in "+-":
if i != 0 and s[i - 1] not in "eE":
return False
elif ch == ".":
if seen_dot or seen_exp:
return False
seen_dot = True
elif ch in "eE":
if seen_exp or not seen_digit:
return False
seen_exp = True
digit_after_exp = False
else:
return False
return seen_digit and digit_after_exp/**
* @param {string} s
* @return {boolean}
*/
var isNumber = function(s) {
s = s.trim();
if (s.length === 0) return false;
let seenDigit = false;
let seenDot = false;
let seenExp = false;
let digitAfterExp = true;
for (let i = 0; i < s.length; i++) {
const c = s[i];
if (c >= '0' && c <= '9') {
seenDigit = true;
if (seenExp) digitAfterExp = true;
} else if (c === '+' || c === '-') {
if (i !== 0 && s[i - 1] !== 'e' && s[i - 1] !== 'E') return false;
} else if (c === '.') {
if (seenDot || seenExp) return false;
seenDot = true;
} else if (c === 'e' || c === 'E') {
if (seenExp || !seenDigit) return false;
seenExp = true;
digitAfterExp = false;
} else {
return false;
}
}
return seenDigit && digitAfterExp;
};中文
题目概述
给定字符串 s，判断它是否是一个合法数字。合法形式包括整数、小数，以及带 e/E 指数部分的科学计数法。
核心思路
这是“语法校验”问题。最稳健的方式是单次扫描状态机：记录是否出现过数字、小数点、指数，以及指数后是否出现数字。
基线解法与不足
如果用大量分支硬拆字符串，容易漏掉边界，比如 ".1"、"3."、"-90E3"，也容易误判 "1e"、"e3"。
最优算法步骤（单遍扫描 + 状态约束）
1）先去掉首尾空格。
2）维护四个标记：seenDigit、seenDot、seenExp、digitAfterExp。
3）遇到数字就更新数字标记；若已进入指数段，还要更新指数后数字标记。
4）小数点只能出现一次，且必须在指数前。
5）e/E 只能出现一次，且前面必须已有数字；出现后先将 digitAfterExp 置为 false。
6）符号位 +/- 只能在开头或紧跟在 e/E 后。
7）出现其他字符直接非法。最后返回 seenDigit && digitAfterExp。
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(1)。
常见陷阱
- 忘记要求指数后必须有数字（"1e" 应为 false）。
- 把中间位置的 +/- 当成合法符号。
- 允许多个小数点，或在指数后还允许小数点。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public boolean isNumber(String s) {
s = s.trim();
if (s.isEmpty()) return false;
boolean seenDigit = false;
boolean seenDot = false;
boolean seenExp = false;
boolean digitAfterExp = true;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (Character.isDigit(c)) {
seenDigit = true;
if (seenExp) digitAfterExp = true;
} else if (c == '+' || c == '-') {
if (i != 0 && s.charAt(i - 1) != 'e' && s.charAt(i - 1) != 'E') return false;
} else if (c == '.') {
if (seenDot || seenExp) return false;
seenDot = true;
} else if (c == 'e' || c == 'E') {
if (seenExp || !seenDigit) return false;
seenExp = true;
digitAfterExp = false;
} else {
return false;
}
}
return seenDigit && digitAfterExp;
}
}func isNumber(s string) bool {
s = strings.TrimSpace(s)
if len(s) == 0 {
return false
}
seenDigit, seenDot, seenExp := false, false, false
digitAfterExp := true
for i := 0; i < len(s); i++ {
c := s[i]
if c >= '0' && c <= '9' {
seenDigit = true
if seenExp {
digitAfterExp = true
}
} else if c == '+' || c == '-' {
if i != 0 && s[i-1] != 'e' && s[i-1] != 'E' {
return false
}
} else if c == '.' {
if seenDot || seenExp {
return false
}
seenDot = true
} else if c == 'e' || c == 'E' {
if seenExp || !seenDigit {
return false
}
seenExp = true
digitAfterExp = false
} else {
return false
}
}
return seenDigit && digitAfterExp
}class Solution {
public:
bool isNumber(string s) {
int l = 0, r = (int)s.size() - 1;
while (l <= r && isspace((unsigned char)s[l])) l++;
while (r >= l && isspace((unsigned char)s[r])) r--;
if (l > r) return false;
bool seenDigit = false, seenDot = false, seenExp = false, digitAfterExp = true;
for (int i = l; i <= r; i++) {
char c = s[i];
if (isdigit((unsigned char)c)) {
seenDigit = true;
if (seenExp) digitAfterExp = true;
} else if (c == '+' || c == '-') {
if (i != l && s[i - 1] != 'e' && s[i - 1] != 'E') return false;
} else if (c == '.') {
if (seenDot || seenExp) return false;
seenDot = true;
} else if (c == 'e' || c == 'E') {
if (seenExp || !seenDigit) return false;
seenExp = true;
digitAfterExp = false;
} else {
return false;
}
}
return seenDigit && digitAfterExp;
}
};class Solution:
def isNumber(self, s: str) -> bool:
s = s.strip()
if not s:
return False
seen_digit = False
seen_dot = False
seen_exp = False
digit_after_exp = True
for i, ch in enumerate(s):
if ch.isdigit():
seen_digit = True
if seen_exp:
digit_after_exp = True
elif ch in "+-":
if i != 0 and s[i - 1] not in "eE":
return False
elif ch == ".":
if seen_dot or seen_exp:
return False
seen_dot = True
elif ch in "eE":
if seen_exp or not seen_digit:
return False
seen_exp = True
digit_after_exp = False
else:
return False
return seen_digit and digit_after_exp/**
* @param {string} s
* @return {boolean}
*/
var isNumber = function(s) {
s = s.trim();
if (s.length === 0) return false;
let seenDigit = false;
let seenDot = false;
let seenExp = false;
let digitAfterExp = true;
for (let i = 0; i < s.length; i++) {
const c = s[i];
if (c >= '0' && c <= '9') {
seenDigit = true;
if (seenExp) digitAfterExp = true;
} else if (c === '+' || c === '-') {
if (i !== 0 && s[i - 1] !== 'e' && s[i - 1] !== 'E') return false;
} else if (c === '.') {
if (seenDot || seenExp) return false;
seenDot = true;
} else if (c === 'e' || c === 'E') {
if (seenExp || !seenDigit) return false;
seenExp = true;
digitAfterExp = false;
} else {
return false;
}
}
return seenDigit && digitAfterExp;
};
Comments