Valid Number Interview Question for Apple

def isNumber(s: str) -> bool:
    """Determines if a given string is a valid number.

    A valid number can be:
    1. An integer number followed by an optional exponent.
    2. A decimal number followed by an optional exponent.

    An integer number is defined with an optional sign '-' or '+' followed by digits.

    A decimal number is defined with an optional sign '-' or '+' followed by:
    1. Digits followed by a dot '.'.
    2. Digits followed by a dot '.' followed by digits.
    3. A dot '.' followed by digits.

    An exponent is defined with an exponent notation 'e' or 'E' followed by an integer number.

    Digits are defined as one or more digits.

    Args:
        s: The input string.

    Returns:
        True if the string is a valid number, False otherwise.
    """

    s = s.strip()
    n = len(s)
    has_digit = False
    has_exponent = False
    has_decimal = False
    index = 0

    # Optional sign
    if index < n and (s[index] == '+' or s[index] == '-'):
        index += 1

    # Digits before decimal point
    while index < n and s[index].isdigit():
        index += 1
        has_digit = True

    # Decimal point
    if index < n and s[index] == '.':
        index += 1
        has_decimal = True

        # Digits after decimal point
        while index < n and s[index].isdigit():
            index += 1
            has_digit = True

    # Exponent
    if index < n and (s[index] == 'e' or s[index] == 'E'):
        if not has_digit:
            return False
        index += 1
        has_exponent = True
        has_digit = False  # Reset digit flag for exponent part

        # Optional sign for exponent
        if index < n and (s[index] == '+' or s[index] == '-'):
            index += 1

        # Digits after exponent
        while index < n and s[index].isdigit():
            index += 1
            has_digit = True

        if not has_digit:
            return False

    return index == n and has_digit


# Example Usage and Testing
if __name__ == '__main__':
    test_cases = [
        "2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7",
        "+6e-1", "53.5e93", "-123.456e789", "abc", "1a", "1e", "e3", "99e2.5",
        "--6", "-+3", "95a54e53", ".1", ".", "46.e3", "+", "-", "e9", "4e+", " -.",
        "46.e+", "3.", " -3.", "+1.e", " -1.", "0e", "0.e",
    ]

    for s in test_cases:
        result = isNumber(s)
        print(f'Input: "{s}", Output: {result}')

Naive Solution

A naive solution might involve a series of if-else statements to check for different possible patterns. This approach would be cumbersome and error-prone because of the numerous conditions to consider.

Optimal Solution

The optimal solution uses a state machine approach. It involves iterating through the string character by character and maintaining flags to track whether we've seen a digit, an exponent, or a decimal point. This allows for a single pass through the string with clear conditions for validity.

def isNumber(s: str) -> bool:
    s = s.strip()
    n = len(s)
    has_digit = False
    has_exponent = False
    has_decimal = False
    index = 0

    # Optional sign
    if index < n and (s[index] == '+' or s[index] == '-'):
        index += 1

    # Digits before decimal point
    while index < n and s[index].isdigit():
        index += 1
        has_digit = True

    # Decimal point
    if index < n and s[index] == '.':
        index += 1
        has_decimal = True

        # Digits after decimal point
        while index < n and s[index].isdigit():
            index += 1
            has_digit = True

    # Exponent
    if index < n and (s[index] == 'e' or s[index] == 'E'):
        if not has_digit:
            return False
        index += 1
        has_exponent = True
        has_digit = False  # Reset digit flag for exponent part

        # Optional sign for exponent
        if index < n and (s[index] == '+' or s[index] == '-'):
            index += 1

        # Digits after exponent
        while index < n and s[index].isdigit():
            index += 1
            has_digit = True

        if not has_digit:
            return False

    return index == n and has_digit

Big(O) Run-time Analysis

The run-time complexity is O(n), where n is the length of the input string s. This is because we iterate through the string at most once. The while loops and conditional checks perform a constant amount of work for each character.

Big(O) Space Usage Analysis

The space complexity is O(1). We use a constant amount of extra space to store flags (e.g., has_digit, has_exponent, has_decimal) and the index. The space used does not depend on the size of the input string.

Edge Cases and Handling

Empty String or Whitespace-only String: The .strip() method handles strings that are entirely whitespace by reducing them to an empty string, which will fail the checks and return False correctly.
String with Only a Sign: Strings like "+" or "-" are invalid because they don't have any digits. The checks ensure that has_digit becomes True at some point.
String with Only a Decimal Point: A string like "." is invalid because it requires digits either before or after the decimal point.
Multiple Decimal Points or Exponents: The algorithm ensures that there is at most one decimal point before the exponent and at most one exponent.
Exponent without Digits: A string like "3e" or "46.e+" is invalid because an exponent must be followed by at least one digit.
Sign after Exponent: The code correctly handles optional signs immediately following the exponent character ('e' or 'E').
Invalid Characters: The algorithm only considers digits, '+', '-', '.', 'e', and 'E'. Any other characters would cause the checks to fail, resulting in False.