Valid Number

Hard

Asked by:

+6

13 views

Topics:

Strings

Given a string s, return whether s is a valid number.

For example, all the following are valid numbers: "2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789", while the following are not valid numbers: "abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53".

Formally, a valid number is defined using one of the following definitions:

An integer number followed by an optional exponent.
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 one of the following definitions:

Digits followed by a dot '.'.
Digits followed by a dot '.' followed by digits.
A dot '.' followed by digits.

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

The digits are defined as one or more digits.

Example 1:

Input: s = "0"

Output: true

Example 2:

Input: s = "e"

Output: false

Example 3:

Input: s = "."

Output: false

Constraints:

1 <= s.length <= 20
s consists of only English letters (both uppercase and lowercase), digits (0-9), plus '+', minus '-', or dot '.'.

Valid Number

Hard

Asked by:

13 views

Topics:

Strings

Given a string s, return whether s is a valid number.

For example, all the following are valid numbers: "2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789", while the following are not valid numbers: "abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53".

Formally, a valid number is defined using one of the following definitions:

An integer number followed by an optional exponent.
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 one of the following definitions:

Digits followed by a dot '.'.
Digits followed by a dot '.' followed by digits.
A dot '.' followed by digits.

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

The digits are defined as one or more digits.

Example 1:

Input: s = "0"

Output: true

Example 2:

Input: s = "e"

Output: false

Example 3:

Input: s = "."

Output: false

Constraints:

1 <= s.length <= 20
s consists of only English letters (both uppercase and lowercase), digits (0-9), plus '+', minus '-', or dot '.'.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input string contain leading or trailing whitespace characters?
Can the input string be empty or null?
Besides digits, '+', '-', 'e', and '.', are there any other characters I should expect in the input string?
How should I handle multiple decimal points or exponents in the string? For example, is '1.1.1' or 'e1e1' valid?
Is a string like '+.' or '-.' valid?

Brute Force Solution

Approach

The brute-force approach involves meticulously checking every possible scenario to determine if a given string represents a valid number. It's like trying out every possible combination of rules and character placements until a valid number is found or all possibilities are exhausted.

Here's how the algorithm would work step-by-step:

Start by considering the simplest case: a single character.
Check if that character alone could be a valid number (e.g., a digit, a plus sign, or a minus sign).
Next, consider pairs of characters, then triplets, and so on, gradually increasing the length of the substring you are examining.
For each substring, methodically check if it conforms to all the rules of what constitutes a valid number, such as the placement of signs, decimal points, and exponents.
If any rule is violated, that particular substring is deemed invalid, and you move on to the next possibility.
Continue this exhaustive process until either a valid number is identified or every possible substring and combination of characters has been examined and deemed invalid.

Code Implementation

def is_valid_number_brute_force(input_string):
    string_length = len(input_string)

    for i in range(string_length):
        for j in range(i, string_length):
            sub_string = input_string[i:j+1]

            # Handle empty substring
            if not sub_string:
                continue

            # Check if the substring is a valid number.
            if is_valid_substring(sub_string):
                return True

    return False

def is_valid_substring(sub_string):
    # Flags to track the presence of digits, exponent, and decimal
    digit_seen = False
    exponent_seen = False
    decimal_seen = False

    for i, char in enumerate(sub_string):
        if char.isdigit():
            digit_seen = True
        elif char in ['+', '-']:
            # Sign can only appear at the beginning or after 'e'
            if i > 0 and sub_string[i-1] != 'e':
                return False
            if i == len(sub_string) - 1:
                return False
        elif char == '.':
            # Decimal point can only appear once and before 'e'
            if decimal_seen or exponent_seen:
                return False
            decimal_seen = True
        elif char == 'e':
            # Exponent can only appear once and must have a digit before it
            if exponent_seen or not digit_seen:
                return False

            exponent_seen = True
            digit_seen = False # Reset digit_seen for the part after 'e'
        else:
            # Invalid character
            return False

    # Must have seen at least one digit
    return digit_seen

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n^3) – The brute-force approach iterates through all possible substrings of the input string of length n. Generating all substrings takes O(n^2) time because we have nested loops to define the start and end indices of each substring. For each of these substrings, we perform a validity check, which in the worst case could involve iterating through all characters in the substring, taking O(n) time. Therefore, the overall time complexity is O(n^2) * O(n) = O(n^3).

Space Complexity

O(1) – The described brute-force approach checks substrings of the input string one by one. It doesn't mention the use of any auxiliary data structures like arrays, lists, or hash maps to store intermediate results or visited states. The algorithm primarily involves iterating through the string and performing checks on substrings, which can be done in place or using a constant amount of extra variables. Therefore, the auxiliary space complexity is constant, regardless of the input string length N.

Optimal Solution

Approach

The challenge is to check if a given text string is a valid number, like checking if it's formatted correctly according to math rules. We'll go through the string one piece at a time, verifying that each part (numbers, signs, decimal points, exponents) fits the allowed patterns for a valid number.

Here's how the algorithm would work step-by-step:

First, handle any extra spaces at the beginning or end of the string by removing them.
Now, check if the string is empty. If it is, it's not a valid number.
Look for an optional plus or minus sign at the beginning of the string. If there is one, that's okay, just continue checking the rest.
Check for the integer part. There should be one or more digits, but it's also acceptable to have zero digits if a decimal part is present.
Check for a decimal point. If there is one, there can be digits after the decimal point, or there might not be. If there are no digits before, make sure there are digits after or it's not a valid number.
Now, check for an exponent part. This starts with 'e' or 'E', followed by an optional plus or minus sign, and then one or more digits. If you find 'e' or 'E', the digits after it are required.
After all those checks, see if there's anything left in the string. If there is, that means there are extra characters that don't belong, so it's not a valid number.
If you've made it through all those checks without problems, then the string is a valid number.

Code Implementation

def is_number(text):
    text = text.strip()
    string_length = len(text)
    if string_length == 0:
        return False

    index = 0
    if text[index] == '+' or text[index] == '-':
        index += 1
        if index == string_length:
            return False

    number_of_digits = 0
    number_of_decimals = 0
    while index < string_length and text[index].isdigit():
        index += 1
        number_of_digits += 1

    if index < string_length and text[index] == '.':
        index += 1
        number_of_decimals += 1

        # Decimal part is optional, but at least one digit must exist.
        while index < string_length and text[index].isdigit():
            index += 1

        if number_of_digits == 0 and index - (number_of_decimals + number_of_digits) == 1:
            return False

    # An exponent can only show up once.
    if index < string_length and (text[index] == 'e' or text[index] == 'E'):
        index += 1

        # Exponent sign is optional
        if index < string_length and (text[index] == '+' or text[index] == '-'):
            index += 1

        exponent_digits = 0
        while index < string_length and text[index].isdigit():
            index += 1
            exponent_digits += 1

        # Exponent digits are required after 'e' or 'E'.
        if exponent_digits == 0:
            return False

    # Check for remaining characters; if any exist, it's invalid.
    if index < string_length:
        return False

    # If we reach this point, the number is valid.
    return True

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string once. It performs a sequence of checks, but each character is visited at most a constant number of times. Therefore, the time complexity is directly proportional to the length of the string, n, resulting in O(n).

Space Complexity

O(1) – The algorithm operates primarily on the input string directly through indexing and character comparisons. While temporary variables may be used to store flags or track positions within the string, the number of such variables remains constant irrespective of the input string's length, denoted as N. No auxiliary data structures like arrays, lists, or hash maps are created that scale with the size of the input. Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
Null or empty string input	Return false immediately as an empty string is not a valid number.
String with only whitespace characters	Trim whitespace and return false if the resulting string is empty.
Leading or trailing whitespace	Trim the string before processing to avoid incorrect parsing.
Multiple signs (+/-) before a number or exponent	Handle only one sign character immediately before a number or exponent, and return false otherwise.
Exponent without an integer or decimal before it	Return false, because there must be a number preceding the exponent.
Decimal point without any digits before or after	Return false, because a decimal point must have at least one digit on either side to be valid in isolation.
Integer overflow during parsing	Check for potential integer overflow during parsing by using long type and ensuring it does not exceed limits before cast to int.
Floating-point precision issues	While this problem generally uses strings, be aware that if converting to float, compare results with tolerance in range of system precision.