Problem Description

Given a string s, determine if it is a valid number. A valid number can be an integer, a decimal, or a number in scientific notation (using 'e' or 'E'). The function should return true if s is a valid number, and false otherwise.

The string s may contain leading or trailing spaces, which should be ignored. The rules for valid numbers include:

• An optional sign (+ or -) at the start or just after an exponent.
• At least one digit (before or after a decimal point).
• At most one decimal point, which cannot appear after an exponent.
• An optional exponent part, which must be followed by an integer (with optional sign).
• No extra characters or spaces within the number.

Examples of invalid numbers: "abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "", ".".

Thought Process

At first glance, this problem can seem overwhelming due to the many possible number formats. A brute-force approach might try to check all possible cases with many if statements, but this quickly becomes messy and error-prone.

Instead, it's better to systematically break down the structure of a valid number. We can think of a number as having three main parts:

• The integer or decimal part (e.g., 3, -0.1, +3.14).
• An optional exponent (e.g., e10, E-3).
• Optional signs at the start or after the exponent.

One way to do this is to use a finite state machine (FSM), but for clarity and maintainability, we can also parse the string step by step, using flags to track what we've seen so far (digits, decimal points, exponents, etc.).

Solution Approach

We'll implement a parser that reads the string from left to right, using boolean flags to keep track of the following:

• seen_digit: Have we seen at least one digit (before or after the decimal)?
• seen_dot: Have we seen a decimal point?
• seen_exp: Have we seen an exponent ('e' or 'E')?
• seen_digit_after_exp: Have we seen at least one digit after the exponent?

1. Trim the input string to remove leading and trailing spaces.
2. Iterate through each character:
   • If it's a digit: set seen_digit (or seen_digit_after_exp if after 'e').
   • If it's a sign (+ or -): it must be at the start or just after an exponent.
   • If it's a decimal point: only allowed if we haven't seen a dot or an exponent yet.
   • If it's an exponent: only allowed if we haven't seen one yet, and we've seen at least one digit so far.
   • Any other character: invalid.
3. At the end, ensure that we've seen at least one digit (and, if there's an exponent, at least one digit after it).

This approach avoids regular expressions and is efficient and readable.

Example Walkthrough

Let's walk through the input " -123.456e789 ":

• Trim spaces: "-123.456e789"
• First character: '-' (valid sign at start)
• Next characters: '1', '2', '3' (digits, set seen_digit)
• Next: '.' (first dot, allowed)
• Next: '4', '5', '6' (more digits)
• Next: 'e' (first exponent, allowed, must have seen digits before this)
• Next: '7', '8', '9' (digits after exponent, set seen_digit_after_exp)
• End of string: check that both seen_digit and seen_digit_after_exp are true.

Result: valid number.

Now, for an invalid example: "1e"

• Trim: "1e"
• '1' is a digit (seen_digit = true).
• 'e' is exponent, allowed after digit.
• End of string, but no digit after exponent (seen_digit_after_exp = false).

Result: invalid number.

Time and Space Complexity

Brute-force approach: If we tried all possible substrings and checked if each is a valid number, the time complexity would be much higher (potentially O(N²) or worse), and the code would be very complex.

Optimized approach (parsing): We scan the string once, using a constant amount of extra space (flags). Thus:

• Time Complexity: O(N), where N is the length of the string, since we process each character once.
• Space Complexity: O(1), since we only use a few boolean variables and do not allocate extra memory proportional to the input size.

Summary

To determine if a string is a valid number, we parse the string step by step, carefully tracking digits, decimal points, exponents, and signs. By using flags to remember what we've seen, we can enforce the rules for valid numbers without resorting to complex regular expressions or brute-force substring checks. This approach is both efficient and robust, and it elegantly handles all the tricky edge cases that can arise with number formats.

Code Implementation

class Solution:
    def isNumber(self, s: str) -> bool:
        s = s.strip()
        if not s:
            return False

        seen_digit = False
        seen_dot = False
        seen_exp = False
        seen_digit_after_exp = True  # True by default unless 'e' is seen

        for i, c in enumerate(s):
            if c.isdigit():
                seen_digit = True
                if seen_exp:
                    seen_digit_after_exp = True
            elif c in ['+', '-']:
                if i != 0 and s[i-1].lower() != 'e':
                    return False
            elif c == '.':
                if seen_dot or seen_exp:
                    return False
                seen_dot = True
            elif c.lower() == 'e':
                if seen_exp or not seen_digit:
                    return False
                seen_exp = True
                seen_digit_after_exp = False  # must see digit after e
            else:
                return False

        return seen_digit and seen_digit_after_exp
      

class Solution {
public:
    bool isNumber(string s) {
        int n = s.size();
        int i = 0;
        // Trim leading spaces
        while (i < n && isspace(s[i])) i++;
        // Trim trailing spaces
        int j = n - 1;
        while (j >= 0 && isspace(s[j])) j--;
        if (i > j) return false;

        bool seen_digit = false;
        bool seen_dot = false;
        bool seen_exp = false;
        bool seen_digit_after_exp = true;

        for (int pos = i; pos <= j; ++pos) {
            char c = s[pos];
            if (isdigit(c)) {
                seen_digit = true;
                if (seen_exp) seen_digit_after_exp = true;
            } else if (c == '+' || c == '-') {
                if (pos != i && tolower(s[pos-1]) != 'e') return false;
            } else if (c == '.') {
                if (seen_dot || seen_exp) return false;
                seen_dot = true;
            } else if (c == 'e' || c == 'E') {
                if (seen_exp || !seen_digit) return false;
                seen_exp = true;
                seen_digit_after_exp = false;
            } else {
                return false;
            }
        }
        return seen_digit && seen_digit_after_exp;
    }
};
      

class Solution {
    public boolean isNumber(String s) {
        s = s.trim();
        if (s.length() == 0) return false;

        boolean seenDigit = false;
        boolean seenDot = false;
        boolean seenExp = false;
        boolean seenDigitAfterExp = true;

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                seenDigit = true;
                if (seenExp) seenDigitAfterExp = true;
            } else if (c == '+' || c == '-') {
                if (i != 0 && Character.toLowerCase(s.charAt(i-1)) != 'e') return false;
            } else if (c == '.') {
                if (seenDot || seenExp) return false;
                seenDot = true;
            } else if (c == 'e' || c == 'E') {
                if (seenExp || !seenDigit) return false;
                seenExp = true;
                seenDigitAfterExp = false;
            } else {
                return false;
            }
        }
        return seenDigit && seenDigitAfterExp;
    }
}
      

var isNumber = function(s) {
    s = s.trim();
    if (s.length === 0) return false;

    let seenDigit = false;
    let seenDot = false;
    let seenExp = false;
    let seenDigitAfterExp = true;

    for (let i = 0; i < s.length; i++) {
        let c = s[i];
        if (c >= '0' && c <= '9') {
            seenDigit = true;
            if (seenExp) seenDigitAfterExp = true;
        } else if (c === '+' || c === '-') {
            if (i !== 0 && s[i-1].toLowerCase() !== 'e') return false;
        } else if (c === '.') {
            if (seenDot || seenExp) return false;
            seenDot = true;
        } else if (c === 'e' || c === 'E') {
            if (seenExp || !seenDigit) return false;
            seenExp = true;
            seenDigitAfterExp = false;
        } else {
            return false;
        }
    }
    return seenDigit && seenDigitAfterExp;
};