LeetCode 65: Valid Number Solution in Python Explained

Problem Statement

LeetCode 65, Valid Number, is a hard-level problem where you’re given a string s. Your task is to determine if it represents a valid number, returning true if it does and false otherwise. A valid number can be an integer or a decimal (with an optional exponent), following specific rules:

  • An integer is a sequence of digits, optionally preceded by a sign (+ or -).
  • A decimal has a decimal point with digits on at least one side, optionally signed.
  • An exponent starts with 'e' or 'E', followed by an integer, and can follow an integer or decimal.
  • No leading zeros (except for "0" itself), and spaces or other characters are invalid.

Constraints

  • 1 <= s.length <= 20: String length is between 1 and 20.
  • s consists of English letters (case-insensitive), digits, '+', '-', '.', and spaces.

Example

Input: s = "0"
Output: true
Explanation: "0" is a valid integer.

Input: s = "e"
Output: false
Explanation: "e" alone is not a number.

Input: s = ".1"
Output: true
Explanation: ".1" is a valid decimal.

Input: s = "3."
Output: true
Explanation: "3." is a valid decimal.

Input: s = "2e10"
Output: true
Explanation: "2e10" is a valid number with exponent.

Understanding the Problem

How do you solve LeetCode 65: Valid Number in Python? For s = "2e10", check if it’s a valid number—here, it’s true as an integer (2) followed by an exponent (e10). The string can include signs, decimals, and exponents, but must follow strict formatting rules. We’ll explore two approaches: a State Machine Solution (optimal and primary) and an Alternative with Regular Expression (concise but less explicit). The state machine method runs in O(n) time with O(1) space, parsing the string character by character.

Solution 1: State Machine Approach (Primary)

Explanation

Use a finite state machine to track the parsing state as we scan the string. Define states based on the components of a valid number (digits, signs, decimal point, exponent), transitioning based on each character. Reject invalid sequences (e.g., multiple decimal points) and ensure the final state is valid.

States:

  • 0: Start (initial state)
  • 1: After sign (before digits)
  • 2: Digits before decimal
  • 3: After decimal point (no digits yet)
  • 4: Digits after decimal
  • 5: After 'e' or 'E'
  • 6: After exponent sign
  • 7: Digits in exponent

Here’s a flow for "2e10":

State 0 -> '2' -> State 2
State 2 -> 'e' -> State 5
State 5 -> '1' -> State 7
State 7 -> '0' -> State 7
End in State 7 (valid)
  1. Define State Transitions.
  • Map each state and character to next state or invalid.
  1. Scan String.
  • Update state per character, reject if invalid.
  1. Check Final State.
  • Valid states: 2 (integer), 4 (decimal), 7 (exponent).
  1. Return Result.

Step-by-Step Example

Example 1: s = "2e10"

We need true.

  • Goal: Validate "2e10" as a number.
  • Result for Reference: true.
  • Start: s = "2e10", state = 0.
  • Step 1: '2'.
    • State 0 -> digit -> State 2.
  • Step 2: 'e'.
    • State 2 -> 'e' -> State 5.
  • Step 3: '1'.
    • State 5 -> digit -> State 7.
  • Step 4: '0'.
    • State 7 -> digit -> State 7.
  • Finish: State 7 is valid, return true.

Example 2: s = ".1"

We need true.

  • Start: state = 0.
  • Step 1: '.'.
    • State 0 -> '.' -> State 3.
  • Step 2: '1'.
    • State 3 -> digit -> State 4.
  • Finish: State 4 is valid, return true.

Example 3: s = "e"

We need false.

  • Start: state = 0.
  • Step 1: 'e'.
    • State 0 -> 'e' -> invalid (no prior number), return false.
  • Finish: Return false.

How the Code Works (State Machine)

Here’s the Python code with line-by-line explanation:

def isNumber(s: str) -> bool:
    # Line 1: Define state transition function
    def next_state(state: int, char: str) -> int:
        if state == 0:  # Start
            if char.isdigit(): return 2
            if char in '+-': return 1
            if char == '.': return 3
            return -1
        elif state == 1:  # After sign
            if char.isdigit(): return 2
            if char == '.': return 3
            return -1
        elif state == 2:  # Digits before decimal
            if char.isdigit(): return 2
            if char == '.': return 4
            if char in 'eE': return 5
            return -1
        elif state == 3:  # After decimal (no digits yet)
            if char.isdigit(): return 4
            return -1
        elif state == 4:  # Digits after decimal
            if char.isdigit(): return 4
            if char in 'eE': return 5
            return -1
        elif state == 5:  # After 'e' or 'E'
            if char.isdigit(): return 7
            if char in '+-': return 6
            return -1
        elif state == 6:  # After exponent sign
            if char.isdigit(): return 7
            return -1
        elif state == 7:  # Digits in exponent
            if char.isdigit(): return 7
            return -1
        return -1

    # Line 2: Initialize state
    state = 0

    # Line 3: Process each character
    for char in s.lower():
        state = next_state(state, char)
        if state == -1:
            return False

    # Line 4: Check if final state is valid
    return state in {2, 4, 7}

Alternative: Regular Expression Approach

Explanation

Use a regular expression to match the string against a pattern defining a valid number. The pattern must account for optional signs, digits before/after a decimal, and an optional exponent with its own sign and digits. This is concise but less explicit about state transitions.

Pattern:

  • ^[+-]?((\d+\.?\d*)|(\.\d+))([eE][+-]?\d+)?$
    • ^[+-]?: Optional sign at start.
    • (\d+\.?\d*)|(\.\d+): Integer/decimal (digits before/after dot).
    • ([eE][+-]?\d+)?: Optional exponent with sign and digits.
    • $: End of string.
  1. Define Pattern.
  2. Match String.
  3. Return Result.

Step-by-Step Example (Alternative)

For "2e10":

  • Start: Pattern = ^[+-]?((\d+\.?\d*)|(\.\d+))([eE][+-]?\d+)?$.
  • Step 1: Match "2e10".
    • Starts with digit "2", no decimal, followed by "e" and "10" -> Matches.
  • Finish: Return true.

For "e":

  • Step 1: No digits before "e", doesn’t match.
  • Finish: Return false.

How the Code Works (Regular Expression)

import re

def isNumberRegex(s: str) -> bool:
    # Line 1: Define regex pattern
    pattern = r'^[+-]?((\d+\.?\d*)|(\.\d+))([eE][+-]?\d+)?$'

    # Line 2: Match string against pattern
    return bool(re.match(pattern, s.strip()))

Complexity

  • State Machine:
    • Time: O(n) – Single pass through string.
    • Space: O(1) – Only state variable.
  • Regular Expression:
    • Time: O(n) – Regex matching is linear in practice.
    • Space: O(1) – Pattern is constant.

Efficiency Notes

State Machine is O(n) time and O(1) space, explicit and optimal for LeetCode 65, offering fine-grained control. Regex is also O(n) time and O(1) space, concise but less transparent, relying on Python’s regex engine.

Key Insights

Tips to master LeetCode 65:

  • State Tracking: Model number components explicitly.
  • Strict Rules: No leading zeros, digits required around decimals/exponents.
  • Flexibility: Handle signs, decimals, and exponents cleanly.

Additional Example

For s = "-1.23e4":

  • Goal: true.
  • State Machine: - (1) -> 1 (2) -> . (4) -> 2 (4) -> 3 (4) -> e (5) -> 4 (7), valid.
  • Result: true.

Edge Cases

  • Empty String: "" – Return false.
  • Invalid Chars: "abc" – Return false.
  • No Digits: ".e1" – Return false.

Final Thoughts

The State Machine solution is a robust choice for LeetCode 65 in Python—precise, efficient, and perfect for parsing numbers. For a related challenge, try LeetCode 64: Minimum Path Sum to switch to grid paths! Ready to validate? Solve LeetCode 65 on LeetCode now and test it with "2e10" or ".1" to master number validation. Dive in and check those digits!