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
Related Courses
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.
Grokking Modern AI Fundamentals
Master the fundamentals of AI today to lead the tech revolution of tomorrow.
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.
;