65. Valid Number - Detailed Explanation

Free Coding Questions Catalog
Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement:

A string is considered a valid number if it can be interpreted as a numeric value. A valid number can contain the following components (in order):

  1. Optional Leading Whitespace:
    Any number of space characters may appear before the number.

  2. Optional Sign:
    A '+' or '-' may precede the number.

  3. Numeric Part (Decimal or Integer):
    The numeric part can be one of the following:

    • Integer: One or more digits (e.g. "123").
    • Decimal Number:
      • Option A: One or more digits followed by a dot '.' and then zero or more digits (e.g. "123." or "123.45").
      • Option B: A dot '.' followed by one or more digits (e.g. ".45").

    Note: At least one digit must appear either before or after the dot.

  4. Optional Exponent Part:
    If present, it starts with 'e' or 'E', followed by an optional sign, and then at least one digit. (e.g. "e10", "E-5")

  5. Optional Trailing Whitespace:
    Any number of space characters may follow the number.

The entire string (after trimming any leading/trailing spaces) must represent a valid number as defined above. No extra characters are allowed.

Example Inputs and Outputs:

  1. Example 1:

    • Input: "0"
    • Output: true
  2. Example 2:

    • Input: " 0.1 "
    • Output: true
    • Explanation: Leading and trailing spaces are allowed.
  3. Example 3:

    • Input: "abc"
    • Output: false
  4. Example 4:

    • Input: "1 a"
    • Output: false
  5. Example 5:

    • Input: "2e10"
    • Output: true
  6. Example 6:

    • Input: " -90e3 "
    • Output: true
  7. Example 7:

    • Input: " 1e"
    • Output: false
  8. Example 8:

    • Input: "e3"
    • Output: false
  9. Example 9:

    • Input: " 6e-1"
    • Output: true
  10. Example 10:

    • Input: "53.5e93"
    • Output: true
  11. Example 11:

    • Input: " --6 "
    • Output: false
  12. Example 12:

    • Input: "-+3"
    • Output: false

Hints for Solving the Problem:

  1. Regular Expression Idea:

    • Think about designing a regular expression that can match the valid patterns described above.
    • A possible regex might look like:
      ^\s*[+-]?((\d+(\.\d*)?)|(\.\d+))([eE][+-]?\d+)?\s*$
      
    • This pattern handles optional spaces, an optional sign, a numeric part that covers both integer and decimal cases, an optional exponent, and trailing spaces.
  2. Finite State Machine (FSM):

    • Alternatively, you can simulate a finite state automaton by scanning the string character by character and ensuring that all transitions follow the rules for a valid number.

    • Think about states for "start," "sign read," "digits before dot," "dot encountered," "digits after dot," "exponent encountered," "exponent sign," and "exponent digits."

  3. Edge Cases to Consider:

    • Strings with only spaces, strings with no digits, multiple signs, or misplaced decimal points or exponent symbols.

Approach 1: Regular Expression

Explanation:

  • Pattern Breakdown:

    • ^\s* : Start of string with optional leading spaces.

    • [+-]? : Optional sign.

    • ((\d+(\.\d*)?)|(\.\d+)) : Either one or more digits with an optional decimal part or a decimal point followed by one or more digits.

    • ([eE][+-]?\d+)? : Optional exponent part starting with e or E, an optional sign, and one or more digits.

    • \s*$ : Optional trailing spaces until end of string.

  • This regex validates the entire string. If the string matches the pattern, it represents a valid number.

Python Code (Regex Approach):

Python3
Python3

. . . .

Java Code (Regex Approach):

Java
Java

. . . .

Approach 2: Finite State Machine / Scanning

Explanation:

  • Overview:
    You can scan the string (after trimming spaces) and use flags to track if you have seen:

    • A digit (at least one required).

    • A dot (decimal point), which can appear at most once.

    • An exponent ('e' or 'E'), which can appear at most once.

    • A sign in appropriate positions (only at the beginning or immediately after an exponent).

  • Algorithm Steps:

    1. Trim the input string.
    2. Use boolean flags: seenDigit, seenDot, and seenExp.
    3. Iterate over each character in the string:
      • If the character is a digit, mark seenDigit as true.

      • If the character is a dot:

        • It cannot appear if already seen or if an exponent was encountered.
      • If the character is e or E:

        • It cannot appear if already seen or if no digit has been seen before.
        • Reset the seenDigit flag for the exponent part.
      • If the character is a sign:

        • It must either be the first character or immediately follow an exponent.
      • Otherwise, if any invalid character is encountered, return false.

    4. Return true if a digit was seen at the end.

Python Code (Scanning Approach):

Python3
Python3

. . . .

Java Code (Scanning Approach):

Java
Java

. . . .

Complexity Analysis:

  • Time Complexity:
    • Both approaches scan the string once, resulting in O(n) time where n is the length of the string.
  • Space Complexity:
    • The regex approach uses O(n) space (depending on the regex engine), whereas the scanning approach uses O(1) extra space.

Edge Cases:

  1. Empty or All Spaces:

    • Strings that are empty or contain only whitespace should return false.
  2. Only Sign or Only Dot:

    • A string like "+" or "." is not a valid number.
  3. Exponent Without Digits:

    • Strings like "1e" or "e3" are invalid.
  4. Multiple Signs or Dots:

    • Strings such as "--6" or "1..2" are invalid.

Common Mistakes:

  1. Not Trimming Spaces:
    • Forgetting to remove leading/trailing spaces may cause false negatives.
  2. Improper Handling of Exponent:
    • Not resetting the digit flag after encountering an exponent can lead to incorrect results.
  3. Overly Permissive Regex:
    • A regex that does not strictly follow the number format rules may validate incorrect strings.

Related Problems for Further Practice:

  1. String to Integer (a to i) (LeetCode 8):
    • Converting a string to an integer involves similar parsing techniques.
  2. Implementing a Calculator:
    • Parsing and evaluating expressions share some of the challenges in validating numerical input.
TAGS
leetcode
CONTRIBUTOR
Design Gurus Team
-

GET YOUR FREE

Coding Questions Catalog

Design Gurus Newsletter - Latest from our Blog
Boost your coding skills with our essential coding questions catalog.
Take a step towards a better tech career now!
Explore Answers
Is 3 months enough for coding?
Conveying domain-specific knowledge in data engineering interviews
What are metaclasses in Python?
Related Courses
Image
Grokking the Coding Interview: Patterns for Coding Questions
Grokking the Coding Interview Patterns in Java, Python, JS, C++, C#, and Go. The most comprehensive course with 476 Lessons.
Image
Grokking Modern AI Fundamentals
Master the fundamentals of AI today to lead the tech revolution of tomorrow.
Image
Grokking Data Structures & Algorithms for Coding Interviews
Unlock Coding Interview Success: Dive Deep into Data Structures and Algorithms.
Image
One-Stop Portal For Tech Interviews.
Copyright © 2025 Design Gurus, LLC. All rights reserved.
;