65. Valid Number - Detailed Explanation

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):

Optional Leading Whitespace:
Any number of space characters may appear before the number.
Optional Sign:
A '+' or '-' may precede the number.
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.
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")
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 1:
- Input: "0"
- Output: true
Example 2:
- Input: " 0.1 "
- Output: true
- Explanation: Leading and trailing spaces are allowed.
Example 3:
- Input: "abc"
- Output: false
Example 4:
- Input: "1 a"
- Output: false
Example 5:
- Input: "2e10"
- Output: true
Example 6:
- Input: " -90e3 "
- Output: true
Example 7:
- Input: " 1e"
- Output: false
Example 8:
- Input: "e3"
- Output: false
Example 9:
- Input: " 6e-1"
- Output: true
Example 10:
- Input: "53.5e93"
- Output: true
Example 11:
- Input: " --6 "
- Output: false
Example 12:
- Input: "-+3"
- Output: false

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.
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."
Edge Cases to Consider:
- Strings with only spaces, strings with no digits, multiple signs, or misplaced decimal points or exponent symbols.

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.

Python3

. . . .

Java

. . . .

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.

Python3

. . . .

Java

. . . .

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.

Empty or All Spaces:
- Strings that are empty or contain only whitespace should return false.
Only Sign or Only Dot:
- A string like "+" or "." is not a valid number.
Exponent Without Digits:
- Strings like "1e" or "e3" are invalid.
Multiple Signs or Dots:
- Strings such as "--6" or "1..2" are invalid.

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

String to Integer (a to i) (LeetCode 8):
- Converting a string to an integer involves similar parsing techniques.
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