Valid Number — Solution in Python, Java & C++
Valid Number solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem, asked at Amazon and Meta.
Valid Number is a hard coding problem on strings and simulation, asked in Amazon, Meta, Nutanix and LinkedIn interviews.
- Difficulty: Hard
- Topics: Strings, Simulation
- Asked at: Amazon, Meta, Nutanix, LinkedIn
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A CodeKairo form field accepts numbers written in plain decimal or scientific notation. Given the text s typed into it, return true if s is a valid number.
The grammar is:
- An integer is an optional sign (
+or-) followed by one or more digits. - A decimal is an optional sign followed by one of: digits then a dot (
7.), digits, a dot and digits (7.25), or a dot and digits (.25). - A valid number is an integer or a decimal, optionally followed by an exponent: the letter
eorEand then an integer.
Nothing else may appear — no spaces, no other letters, no second dot, and the exponent may not hold a dot.
So "2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1" and "53.5e93" are valid, while "abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3" and "95a54e53" are not.
Example 1
Input: s = "-12.5e+3"
Output: true
Explanation: A signed decimal `-12.5` followed by the exponent `e+3`.
Example 2
Input: s = ".e7"
Output: false
Explanation: The part before the exponent has no digit at all.
Example 3
Input: s = "6+1"
Output: false
Explanation: A sign may only appear at the very start or right after `e`/`E`.
Constraints
1 <= s.length <= 20s consists of English letters, digits, '+', '-' and '.'
Hints for Valid Number
Hint 1
Scan once from left to right and remember three facts: whether you have seen a digit, a dot, and an exponent marker.
Hint 2
A sign is legal only at index 0 or immediately after
e/E. A dot is legal only if no dot and no exponent came before it.Hint 3
An
e/Eis legal only once and only after at least one digit; when you see it, reset the "seen a digit" flag so the exponent must have its own digits. The answer is that flag at the end.
How to solve Valid Number
The grammar is regular, so a single left-to-right scan with three flags (digit, dot, exp) decides it — every rule of the grammar becomes a local check on the current character.
Approach
- Set
digit = dot = exp = false. - For each character
cat indexi: if it is a digit, setdigit = true. - If it is
+or-: it is valid only wheni == 0or the previous character ise/E; otherwise returnfalse. - If it is
.: returnfalseifdotorexpis already set; otherwise setdot = true. - If it is
eorE: returnfalseifexpis set ordigitis not; otherwise setexp = trueand resetdigit = false. - Any other character returns
false. After the scan, returndigit.
Why it works
The flags capture exactly what the grammar needs to know about the prefix read so far. Before the exponent, digit records whether the mantissa has at least one digit (which every decimal and integer form requires) and dot forbids a second dot. Resetting digit at the exponent forces the integer after e to contain a digit, while exp forbids a second exponent and any dot after it. Signs are only accepted at the two positions where the grammar allows them.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
"4."and".5"are valid but"."alone is not — require at least one digit in the mantissa, not on each side of the dot.- Forgetting to reset the digit flag at
eaccepts"1e"and"1e+". - Library number parsers accept extras such as
Infinity, hex or surrounding spaces — implement the grammar instead.
Reference solution
Python
def isNumber(s: str) -> bool:
digit = dot = exp = False
for i, c in enumerate(s):
if "0" <= c <= "9":
digit = True
elif c == "+" or c == "-":
if i > 0 and s[i - 1] not in "eE":
return False
elif c == ".":
if dot or exp:
return False
dot = True
elif c == "e" or c == "E":
if exp or not digit:
return False
exp = True
digit = False
else:
return False
return digitJava
public static boolean isNumber(String s) {
boolean digit = false, dot = false, exp = false;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c >= '0' && c <= '9') {
digit = true;
} else if (c == '+' || c == '-') {
if (i > 0 && s.charAt(i - 1) != 'e' && s.charAt(i - 1) != 'E') return false;
} else if (c == '.') {
if (dot || exp) return false;
dot = true;
} else if (c == 'e' || c == 'E') {
if (exp || !digit) return false;
exp = true;
digit = false;
} else {
return false;
}
}
return digit;
}C++
bool isNumber(string s) {
bool digit = false, dot = false, exp = false;
for (int i = 0; i < (int)s.size(); i++) {
char c = s[i];
if (c >= '0' && c <= '9') {
digit = true;
} else if (c == '+' || c == '-') {
if (i > 0 && s[i - 1] != 'e' && s[i - 1] != 'E') return false;
} else if (c == '.') {
if (dot || exp) return false;
dot = true;
} else if (c == 'e' || c == 'E') {
if (exp || !digit) return false;
exp = true;
digit = false;
} else {
return false;
}
}
return digit;
}JavaScript
var isNumber = function(s) {
var digit = false, dot = false, exp = false;
for (var i = 0; i < s.length; i++) {
var c = s.charAt(i);
if (c >= "0" && c <= "9") {
digit = true;
} else if (c === "+" || c === "-") {
if (i > 0 && s.charAt(i - 1) !== "e" && s.charAt(i - 1) !== "E") return false;
} else if (c === ".") {
if (dot || exp) return false;
dot = true;
} else if (c === "e" || c === "E") {
if (exp || !digit) return false;
exp = true;
digit = false;
} else {
return false;
}
}
return digit;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings