LeetCode 65: Valid Number

Problem Restatement

We are given a string s.

We need to return true if s represents a valid number. Otherwise, return false.

A valid number can have:

1. A decimal number or an integer
2. Optionally, an exponent part using e or E, followed by an integer

The official examples include valid strings such as:

"2"
"0089"
"-0.1"
"+3.14"
"4."
"-.9"
"2e10"
"-90E3"
"3e+7"
"+6e-1"
"53.5e93"
"-123.456e789"

And invalid strings such as:

"abc"
"1a"
"1e"
"e3"
"99e2.5"
"--6"
"-+3"
"95a54e53"

The official constraints are 1 <= s.length <= 20, and s contains only English letters, digits, +, -, or ..

Input and Output

Function shape:

def isNumber(s: str) -> bool:
    ...

Examples

For:

s = "0"

The answer is:

True

"0" is an integer.

For:

s = "e"

The answer is:

False

An exponent marker cannot stand alone.

For:

s = "."

The answer is:

False

A decimal point alone has no digits.

For:

s = ".1"

The answer is:

True

A decimal number may start with a dot if at least one digit follows it.

First Thought: Split by Cases

We could try to write many special cases:

integer
signed integer
decimal
signed decimal
decimal with exponent
integer with exponent
signed exponent

This quickly becomes messy.

A better approach is to scan the string once and track what we have already seen.

Key Insight

There are only a few important facts to remember while scanning:

The exponent is special.

After e or E, the string must contain an integer. That means:

1. No dot after exponent
2. Optional sign after exponent
3. At least one digit after exponent

To enforce the third rule, when we see e or E, we reset:

seen_digit = False

Then the final answer is valid only if seen_digit is true at the end.

Character Rules

For each character:

The important subtle case is exponent.

This is invalid:

"1e"

When we see e, we reset seen_digit to False. Since no digit appears after it, the final result is False.

This is valid:

"1e-3"

The sign is allowed because it appears immediately after e.

Then 3 makes the exponent integer valid.

Algorithm

Initialize:

seen_digit = False
seen_dot = False
seen_exp = False

Scan each character ch at index i.

If ch is a digit:

seen_digit = True

If ch is + or -, it is valid only when:

i == 0 or s[i - 1] in "eE"

If ch is ., it is invalid if:

seen_dot or seen_exp

Otherwise mark seen_dot = True.

If ch is e or E, it is invalid if:

seen_exp or not seen_digit

Otherwise:

seen_exp = True
seen_digit = False

At the end, return seen_digit.

Correctness

The algorithm accepts signs only at the beginning of the string or immediately after an exponent marker. These are exactly the two places where the grammar allows signs.

The algorithm accepts a decimal point only before any exponent and only once. This matches the rule that a decimal number may contain one dot, while the exponent part must be an integer.

The algorithm accepts e or E only after at least one digit has appeared and only once. This ensures the base part exists and prevents multiple exponents.

After reading an exponent marker, the algorithm resets seen_digit to False. Therefore the final return requires at least one digit after the exponent. This rejects strings like "1e" and "1e+".

At the end, seen_digit is true exactly when the current required numeric part contains at least one digit. Therefore the algorithm returns true exactly for valid numbers.

Complexity

Implementation

class Solution:
    def isNumber(self, s: str) -> bool:
        seen_digit = False
        seen_dot = False
        seen_exp = False

        for i, ch in enumerate(s):
            if ch.isdigit():
                seen_digit = 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
                seen_digit = False

            else:
                return False

        return seen_digit

Code Explanation

We start with three flags:

seen_digit = False
seen_dot = False
seen_exp = False

A digit is always allowed:

if ch.isdigit():
    seen_digit = True

A sign is allowed only at the start or right after exponent:

elif ch in "+-":
    if i != 0 and s[i - 1] not in "eE":
        return False

A dot is allowed only once and only before exponent:

elif ch == ".":
    if seen_dot or seen_exp:
        return False
    seen_dot = True

An exponent is allowed only once and only after a valid numeric base:

elif ch in "eE":
    if seen_exp or not seen_digit:
        return False
    seen_exp = True
    seen_digit = False

The reset is necessary because the exponent must have digits after it.

Any other character makes the string invalid:

else:
    return False

Finally:

return seen_digit

This rejects ".", "e", "1e", and "1e+".

Testing

def run_tests():
    s = Solution()

    valid = [
        "2",
        "0089",
        "-0.1",
        "+3.14",
        "4.",
        "-.9",
        "2e10",
        "-90E3",
        "3e+7",
        "+6e-1",
        "53.5e93",
        "-123.456e789",
        "0",
        ".1",
    ]

    invalid = [
        "abc",
        "1a",
        "1e",
        "e3",
        "99e2.5",
        "--6",
        "-+3",
        "95a54e53",
        ".",
        "+.",
        "1e+",
        "1e-",
        "1..2",
        "1e2e3",
    ]

    for text in valid:
        assert s.isNumber(text) is True, text

    for text in invalid:
        assert s.isNumber(text) is False, text

    print("all tests passed")

run_tests()