65. Valid Number — DSA Atlas

HardTrie and Advanced String SearchManual parser / finite state machineGrammar validation by ordered scan

Valid Number

Given a string s, return true if it is a valid number. A valid number is an optional sign followed by a decimal (a run of digits containing at most one dot and at least one digit) or an integer, optionally followed by an exponent: 'e' or 'E', an optional sign, and one or more digits. No other characters are allowed.

Open official problem prompt ↗

In plain English

Decide whether a string conforms exactly to the grammar of a signed decimal or integer with an optional scientific exponent.

Picture it like this

Like a passport control that checks each field in a fixed order - nationality prefix, main number, optional visa stamp - and rejects the traveler if any field is malformed or if there are extra pages after the last valid one.

Example

Input: s = "3.14"
Output: true
Why: '3.14' is a decimal with one dot and digits present, and it has no exponent, so it is valid.

Constraints

1 <= s.length <= 20s consists of only English letters (both cases), digits, '+', '-', '.', 'e', and 'E'

Pattern lesson

See the pattern, then code

Grammar validation by ordered scan

↗

Trie and Advanced String Search

Repeated prefix lookup, autocomplete, dictionary search, or many-word matching.. A valid number is exactly: optional sign, a mantissa that must contain at least one digit and at most one dot, then an optional exponent whose body must be a non-empty run of digits. Consume each part in order and require the scan to end exactly at the string's end.

New words, made simpleKnow these before the algorithm

Mantissa: The main numeric part before any exponent, e.g. '3.14' in '3.14e2'.
Exponent: The 'e'/'E' section giving a power of ten; its body must be a plain integer.
Finite state machine: A model that moves between a fixed set of states as it reads characters, accepting only on valid end states.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Regular expression

Concise but error-prone to get exactly right and hard to explain in an interview.

Match the full string against a pattern like [+-]?(\\d+\\.?\\d*|\\.\\d+)([eE][+-]?\\d+)?.

Time O(n)Space O(1)

Best choiceOrdered manual scan

Transparent, debuggable, and encodes every rule explicitly.

Walk one index through sign, mantissa, and optional exponent, tracking digit and dot counts.

Time O(n)Space O(1)

The rule we keep true

Invariant

After each phase completes, index i points just past the last character that phase legally consumed, and the mantissa is only accepted once it is known to hold at least one digit and no more than one dot.

Why this is correct

Reasoning

Every valid number decomposes uniquely into sign, mantissa, and optional exponent in that order; consuming them greedily and then requiring i == n rejects any string with malformed parts or trailing garbage, which is exactly the grammar's definition.

The algorithm in three movesSay these aloud before coding

1Consume an optional leading sign

mantissa scan: digits = 3, dots = 1

2Scan a run of digits and dots, counting each

no 'e' section present

3Reject if there are zero digits or more than one dot in the mantissa

i reaches n = 4 -> valid

4If an 'e'/'E' follows, consume it, an optional sign, and require at least one exponent digit

5Return true only if the whole string was consumed

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Read'3'

2 · AskLeading '+' or '-'?

3 · Update statei = 0

4 · ResultNo sign, i stays 0

Key takeaway

The mantissa '3.14' has one dot and three digits; the scan consumes the entire string.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 4-5Optional leading sign
At most one '+' or '-' before the mantissa.
2
Lines 6-12Mantissa scan
Count digits and dots in a single run of digit/dot characters.
3
Lines 13-14Mantissa validity
Need at least one digit and no more than one dot.
4
Lines 15-24Optional exponent
'e'/'E', optional sign, then at least one digit are all required together.
5
Lines 25Full-consumption check
Any leftover character means invalid.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

'.' alone is invalid (no digit)
'e' or '3e' is invalid (empty exponent body)
'+.8' and '46.' are valid decimals
'-90E3' and '.1' are valid
'99e2.5' is invalid because the exponent must be an integer
Trailing letters like '3a' are invalid

Common beginner mistakes

Allowing a dot inside the exponent
Accepting a sign in the middle of the mantissa
Forgetting to require at least one digit somewhere in the mantissa
Not enforcing i == n, which lets trailing junk slip through
Treating a bare '+' or '-' as valid

Check your understanding

Why is the single check 'digits == 0 or dots > 1' enough to validate the whole mantissa regardless of where the dot sits?

PyPython 3 · solution.py

Optimal

1class Solution:2    def isNumber(self, s: str) -> bool:3        i, n = 0, len(s)4        if i < n and s[i] in '+-':5            i += 16        digits, dots = 0, 07        while i < n and (s[i].isdigit() or s[i] == '.'):8            if s[i] == '.':9                dots += 110            else:11                digits += 112            i += 113        if digits == 0 or dots > 1:14            return False15        if i < n and s[i] in 'eE':16            i += 117            if i < n and s[i] in '+-':18                i += 119            exp_digits = 020            while i < n and s[i].isdigit():21                exp_digits += 122                i += 123            if exp_digits == 0:24                return False25        return i == n

Time complexityO(n)Optimized

Space complexityO(1)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonLinkedInFacebookGoogle

Valid Number

Valid Number

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Trie and Advanced String Search