Valid Number is not an algorithms problem. There is no clever insight and no complexity to
improve — it is O(n) the moment you start, and it stays there. What it tests is whether
you can take an ambiguous specification, pin it down with questions, and turn it into code that does
not sprawl. That is a genuinely different skill, and plenty of strong algorithmic candidates handle
it badly.
The problem
Decide whether a string is a valid number. A valid number is:
- an optional sign,
+or-, then - an integer (
digits) or a decimal (digits.digits,digits.or.digits), then - optionally,
eorEfollowed by a signed integer.
valid: "2" "0089" "-0.1" "+3.14" "4." "-.9" "2e10"
"-90E3" "3e+7" "+6e-1" "53.5e93" "-123.456e789"
invalid: "abc" "1a" "1e" "e3" "99e2.5" "--6"
"-+3" "95a54e53" "." "+" "" "4e+"Read the invalid list carefully — it is where the specification actually lives.
"4." is valid but "." is not; "3e+7" is valid but
"99e2.5" is not.
Ask before you code
The statement above is precise because someone made it precise. In an interview it usually is not, and the first move is to nail down the edges out loud:
- Is leading or trailing whitespace allowed? (Older versions of this problem allowed it.)
- Is a lone
"."a number? What about"4."? - May the exponent have a decimal point? A sign?
- Is
"Infinity"or"NaN"in scope? Hex? Underscores, as in Java literals?
Asking three of those is worth more than a fast solution. It is the behaviour the problem is selecting for, and stating the assumptions you are coding to protects you when a test case disagrees.
Three flags and a pass
Resist the finite-state machine. It is the textbook answer and drawing it correctly under pressure takes longer than the whole interview slot. A single pass carrying three booleans is equivalent, shorter, and far easier to defend line by line.
seenDigit any digit so far in the CURRENT part (mantissa, or exponent)
seenDot a '.' has appeared
seenExp an 'e' or 'E' has appearedThen each character type has exactly one rule:
digit always fine seenDigit = true
sign only at index 0, or immediately after e/E
anywhere else -> invalid
'.' invalid if seenDot (two points)
invalid if seenExp (exponent must be an integer)
otherwise seenDot = true
'e'/'E' invalid if seenExp (two exponents)
invalid if !seenDigit (nothing to raise: "e3", ".e1")
otherwise seenExp = true, seenDigit = FALSE
other invalid
at the end: valid if seenDigitTwo lines carry almost all the difficulty.
Resetting seenDigit to false on e is what forces digits
to follow the exponent. Without it "1e" passes. With it, the flag means "digits in the
part I am currently reading", and the final check covers both the mantissa and the exponent with one
test.
Requiring seenDigit before e is what rejects
"e9" and ".e1". And because seenDot is never reset,
"99e2.5" is rejected by the seenExp check on '.' rather than
needing its own rule.
Java
class Solution {
public boolean isNumber(String s) {
boolean seenDigit = false, seenDot = false, seenExp = false;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c >= '0' && c <= '9') {
seenDigit = true;
} else if (c == '+' || c == '-') {
// Only leading, or immediately after the exponent marker.
if (i > 0 && s.charAt(i - 1) != 'e' && s.charAt(i - 1) != 'E') return false;
} else if (c == '.') {
if (seenDot || seenExp) return false; // ".." or an exponent with a point
seenDot = true;
} else if (c == 'e' || c == 'E') {
if (seenExp || !seenDigit) return false; // "1e2e3", or "e9" with no mantissa
seenExp = true;
seenDigit = false; // the exponent needs its own digits
} else {
return false;
}
}
return seenDigit;
}
}Note what is not there: no whitespace trimming, no length special cases, no separate
handling for the empty string. An empty string never enters the loop and seenDigit is
false, so it returns false for the right reason rather than by accident.
Python
class Solution:
def isNumber(self, s: str) -> bool:
seen_digit = seen_dot = seen_exp = False
for i, c in enumerate(s):
if c.isdigit():
seen_digit = True
elif c in "+-":
if i > 0 and s[i - 1] not in "eE":
return False
elif c == ".":
if seen_dot or seen_exp:
return False
seen_dot = True
elif c in "eE":
if seen_exp or not seen_digit:
return False
seen_exp, seen_digit = True, False
else:
return False
return seen_digitOne caution on c.isdigit(): it is true for characters like '²' and
various non-ASCII digits, so it is subtly wider than '0' <= c <= '9'. It is fine
under this problem's ASCII constraint, but it is exactly the kind of assumption to state rather than
absorb — and if the interviewer asks about Unicode input, the explicit range comparison is the
answer.
The regex answer
^[+-]?((\d+\.?\d*)|(\.\d+))([eE][+-]?\d+)?$Correct, and worth writing on the whiteboard because it documents the grammar compactly. It is a poor primary answer: an interviewer cannot tell whether you understand the cases or copied a pattern, you cannot walk it line by line, and a typo in it is invisible.
Offer it as a cross-check on your own solution — "here is the grammar I implemented" — rather than instead of one.
Complexity
| Time | Space | |
|---|---|---|
| Single pass | O(n) | O(1) |
Nothing to optimise. When a problem has no interesting complexity, the interviewer is grading correctness and structure — which means clear names, one rule per branch, and edge cases you raised yourself.
What the interviewer is checking
- That you clarify the specification before writing anything.
"1e"and"4e+"— that the exponent must be followed by digits."e9"— that something must precede the exponent."99e2.5"— no decimal point inside an exponent."."and"+"invalid, while"4."and"-.9"are valid.- Signs allowed only at the start or right after
e. - That the code stays flat instead of nesting, and that you can defend each branch.