We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Valid Number

Number: 65

Difficulty: Hard

Paid? No

Companies: Meta, Nutanix, LinkedIn, Amazon, Apple

Problem Description

Given a string s, determine if it represents a valid number. A valid number can be an integer or a decimal number, optionally followed by an exponent (indicated by 'e' or 'E' and an integer). The string may include an optional leading '+' or '-' sign. There are various formats allowed including numbers like "2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", and "-123.456e789". Some examples of invalid numbers are "abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53".

Key Insights

  • The number may be split into three parts: a base that can be an integer or a decimal, an optional exponent part, and optional signs preceding these parts.
  • For decimals, ensure proper placement of the dot and digits (at least one digit must be present either before or after the dot).
  • The exponent part (if present) must be a valid integer following 'e' or 'E'.
  • A straightforward solution is to use either a regular expression or to implement a finite state machine (FSM) that validates each character according to the allowed transitions.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string, since we scan through the string once.
Space Complexity: O(1), using only a fixed number of variables for state management.

Solution

We solve this problem by parsing the string according to the rules defined. A regular expression approach can elegantly capture all the allowed formats. The regex explicitly handles:

  • An optional leading sign.
  • Either an integer or a decimal component (where the decimal must have a dot and at least one digit on one side).
  • An optional exponent part starting with 'e' or 'E' followed by an optional sign and digits.

This approach works by matching the entire string against the regex pattern. If the match succeeds, the string represents a valid number.

Alternatively, one may use a finite state machine that transitions between states such as "start", "integer", "point", "fraction", "exponent", "exponent_sign", and "exponent_number". However, the regex approach is more concise and straightforward in this case.

Code Solutions

import re

def isNumber(s: str) -> bool:
    # Regular expression pattern for validating a number
    # Explanation:
    # ^[+-]?               -> Optional leading sign.
    # (?:\d+\.\d*|\.\d+|\d+) -> Either:
    #                           - one or more digits followed by a dot and zero or more digits,
    #                           - a dot followed by one or more digits,
    #                           - or just one or more digits (integer).
    # (?:[eE][+-]?\d+)?     -> Optional exponent part: 'e' or 'E' followed by an optional sign and at least one digit.
    # $                    -> End of string.
    pattern = re.compile(r'^[+-]?(?:\d+\.\d*|\.\d+|\d+)(?:[eE][+-]?\d+)?$')
    
    # Use fullmatch to ensure the entire string is matched.
    return bool(pattern.fullmatch(s))

# Example usage:
print(isNumber("2"))         # Expected output: True
print(isNumber("e"))         # Expected output: False
print(isNumber("."))         # Expected output: False
← Back to All Questions