65. Valid Number

HardString
Leetcode Link

Problem Description

The problem is about verifying if a given string s represents a valid number according to certain rules defined for decimal numbers and integers. A valid number can be an integer or a decimal number, optionally followed by an exponent. An exponent consists of an 'e' or 'E' followed by an integer. A decimal number includes an optional sign ('+' or '-'), digits, and a decimal point in specific arrangements. An integer consists of an optional sign and one or more digits. A valid number must conform to these rules to be considered as such.

Valid examples include: "2", "0089", "-0.1", "4.", "2e10", "3e+7", "53.5e93", etc. Invalid examples are: "abc", "1a", "1e", "--6", "95a54e53", etc.

The aim is to write a function that takes the string s and returns true if s represents a valid number, otherwise false.

Intuition

The solution approach starts by checking the string for the necessary conditions and the optional components, like sign, decimal point, and exponent, in their correct order and format.

  1. We scan the string to find a valid sequence of digits, accepting an optional leading sign.
  2. Next, we look for a decimal point, but we must handle it carefully since it might be part of a valid decimal or an invalid character sequence.
  3. Then, if we have an exponent symbol ('e' or 'E'), it must be followed by an integer (optionally with its own sign), but cannot be the first or the last character.
  4. Along the way, we must also reject any characters that do not belong in a number, like alphabetic characters other than 'e' or 'E', or unexpected symbols.

The given solution uses a while loop to iterate through each character and apply these rules to determine the validity of the string. It keeps track of whether a decimal point or an exponent has been seen to ensure they are not repeated and to validate their positions in the string.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which two pointer technique does Quick Sort use?

Solution Approach

The solution uses string scanning and simple conditional checking to validate the format of the number.

  • The algorithm begins by iterating over each character of the string s while keeping count of decimal points and exponents encountered.
  • A sign character is allowed at the beginning of s or immediately after an exponent marker.
  • Initially, an attempt is made to skip the optional sign at the beginning of the string, as it does not impact the format in terms of digits or decimal places.
  • An edge case is handled where a string could be just a sign or could start with a decimal point with no digits following or preceding it or followed by an exponent marker; such strings are considered invalid.

Next, a while loop commences which iterates over each remaining character:

  • It checks for the presence of a decimal point. If a decimal point is found, it confirms whether one has already been encountered or if an exponent has been encountered prior. Since a number can only have one decimal point and it cannot appear after an exponent, such cases are flagged as invalid by returning false.

  • If an 'e' or 'E' is encountered, it checks if an exponent has already been seen (as there can only be one) or if it's at the beginning of the string (there should be digits before an exponent) or at the end of the string (there must be an integer part following it).

  • If the character immediately following an exponent is a sign, it is allowed, but there must be digits following this sign (an exponent cannot be followed by a sign that is the last character).

  • Any non-numeric character encountered (excluding signs immediately following an exponent) invalidates the number, triggering an immediate return of false.

  • The loop continues until all characters are verified. If the string passes all checks, the function returns true, indicating that s is a valid number.

This algorithm neither necessitates complex data structures nor applies intricate patterns, relying instead on sequential character checking and state tracking with simple boolean flags indicating the presence of specific characters ('.', 'e', 'E'). Notably, the solution is fine-tuned to the specific validation rules set out in the problem description.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

Example Walkthrough

Let's take the string s = "3.5e+2" and walk through the steps to determine if it represents a valid number according to the solution approach:

  1. The algorithm starts by looking for an optional sign. The first character is '3', which is a valid digit and not a sign, so the algorithm moves on.
  2. As the algorithm continues, it finds a decimal point after '3'. Since no decimal point has been encountered yet and an exponent has not appeared, this is still a potential valid number.
  3. The next character is '5', which is a digit, so the reading continues without any issue.
  4. Following the digit '5', the algorithm encounters an 'e', indicating the start of an exponent. Since this is the first exponent character and there have been digits before, the pattern is still valid.
  5. It then sees a '+', which is an allowed sign for the exponent as long as it's immediately after the 'e' and is not the last character in the string.
  6. Finally, the algorithm finds a '2', which is a digit following the exponent and its sign. This confirms a valid integer part of the exponent.

Since the end of the string is reached without any invalid character or sequence, the algorithm concludes that s = "3.5e+2" is a valid number and returns true. This example successfully represents a number with both a decimal and an exponent, including an optional sign for the exponent.

Solution Implementation

1class Solution:
2    def isNumber(self, s: str) -> bool:
3        # Length of the input string.
4        length = len(s)
5        # Start index for traversing the string.
6        index = 0
7      
8        # Check for optional sign at the beginning.
9        if s[index] in '+-':
10            index += 1
11      
12        # Empty string after a sign or no numeric part is invalid.
13        if index == length:
14            return False
15      
16        # Single dot without digits or dot directly followed by exponent is invalid.
17        if s[index] == '.' and (index + 1 == length or s[index + 1] in 'eE'):
18            return False
19      
20        # Counters for dots and exponent characters.
21        dot_count = exponent_count = 0
22      
23        # Traverse the string starting from the current index.
24        while index < length:
25            if s[index] == '.':
26                # If there's already a dot or an exponent, it's invalid.
27                if exponent_count or dot_count:
28                    return False
29                dot_count += 1
30            elif s[index] in 'eE':
31                # If there's already an exponent, or this is the first character, or there isn't a number following, it's invalid.
32                if exponent_count or index == 0 or index == length - 1:
33                    return False
34                exponent_count += 1
35                # Check for an optional sign after the exponent.
36                if s[index + 1] in '+-':
37                    index += 1
38                    # If the string ends after the sign, it's invalid.
39                    if index == length - 1:
40                        return False
41            # Non-numeric, non-dot, and non-exponent characters are invalid.
42            elif not s[index].isdigit():
43                return False
44            index += 1
45      
46        # If all checks pass, the string represents a valid number.
47        return True
48
1class Solution {
2    public boolean isNumber(String s) {
3        int length = s.length();
4        int index = 0;
5
6        // Check for an optional sign at the beginning
7        if (s.charAt(index) == '+' || s.charAt(index) == '-') {
8            index++;
9        }
10
11        // Check if the string is non-empty after optional sign
12        if (index == length) {
13            return false;
14        }
15
16        // Check for string starting with a dot followed by e/E or end of string
17        if (s.charAt(index) == '.' && (index + 1 == length || s.charAt(index + 1) == 'e' ||
18            s.charAt(index + 1) == 'E')) {
19            return false;
20        }
21
22        int dotCount = 0; // Count of dots in the string
23        int eCount = 0;   // Count of 'e's or 'E's in the string
24
25        // Iterate over the characters in the string
26        for (int i = index; i < length; ++i) {
27            char currentChar = s.charAt(i);
28
29            if (currentChar == '.') {
30                // If there's an 'e/E' before the dot or it's a second dot, it's invalid
31                if (eCount > 0 || dotCount > 0) {
32                    return false;
33                }
34                dotCount++;
35            } else if (currentChar == 'e' || currentChar == 'E') {
36                // Check for multiple 'e/E', 'e/E' at start/end or directly after a sign
37                if (eCount > 0 || i == index || i == length - 1) {
38                    return false;
39                }
40                eCount++;
41                // Check for a sign immediately after 'e/E'
42                if (s.charAt(i + 1) == '+' || s.charAt(i + 1) == '-') {
43                    // Skip the next character if it's a sign
44                    // If it leads to end of the string, it's invalid
45                    if (++i == length - 1) {
46                        return false;
47                    }
48                }
49            } else if (currentChar < '0' || currentChar > '9') {
50                // If the character is not a digit, it's invalid
51                return false;
52            }
53        }
54        // If all checks pass, it's a number
55        return true;
56    }
57}
58
1class Solution {
2public:
3    // Function to determine if a given string is a valid number
4    bool isNumber(string s) {
5        int length = s.size(); // Store the size of the string
6        int index = 0; // Start index for scanning the string
7
8        // Optional sign in front; increment index if it exists
9        if (s[index] == '+' || s[index] == '-') index++;
10      
11        // If string is empty or has only a sign, return false
12        if (index == length) return false;
13      
14        // If string starts with a dot and is not followed by a digit or exponent,
15        // it is not a valid number
16        if (s[index] == '.' && (index + 1 == length || s[index + 1] == 'e' || s[index + 1] == 'E')) return false;
17
18        int dotCount = 0, eCount = 0; // Counters for the dots and exponents encountered
19
20        // Loop over the rest of the string
21        for (int j = index; j < length; ++j) {
22            if (s[j] == '.') {
23                // If we encounter a dot after an exponent or if it's a second dot, it's invalid
24                if (eCount || dotCount) return false;
25                dotCount++; // Increment dot counter
26            } else if (s[j] == 'e' || s[j] == 'E') {
27                // If we encounter an exponent after another exponent, or if it's at the start
28                // or end of the number, it's invalid
29                if (eCount || j == index || j == length - 1) return false;
30                eCount++; // Increment exponent counter
31                // Skip the sign of the exponent part if it's there
32                if (s[j + 1] == '+' || s[j + 1] == '-') {
33                    if (++j == length - 1) return false; // If only a sign follows the exponent, it's invalid
34                }
35            } else if (s[j] < '0' || s[j] > '9') {
36                // If the character is not a digit, it's invalid
37                return false;
38            }
39        }
40        // If all conditions are met, it's a valid number
41        return true;
42    }
43};
44
1// Determines if a given string is a valid number
2function isNumber(s: string): boolean {
3    // Store the size of the string
4    const length: number = s.length;
5    // Start index for scanning the string
6    let index: number = 0;
7
8    // Optional sign in front; increment index if it exists
9    if (s[index] === '+' || s[index] === '-') index++;
10  
11    // If string is empty or has only a sign, return false
12    if (index === length) return false;
13  
14    // If string starts with a dot and is not followed by a digit or exponent, it is not a valid number
15    if (s[index] === '.' && (index + 1 === length || s[index + 1] === 'e' || s[index + 1] === 'E')) return false;
16
17    // Counters for the dots and exponents encountered
18    let dotCount: number = 0;
19    let eCount: number = 0;
20
21    // Loop over the rest of the string
22    for (let j = index; j < length; j++) {
23        if (s[j] === '.') {
24            // If we encounter a dot after an exponent or if it's a second dot, it's invalid
25            if (eCount || dotCount) return false;
26            dotCount++; // Increment dot counter
27        } else if (s[j] === 'e' || s[j] === 'E') {
28            // If we encounter an exponent after another exponent, or if it's at the start or end of the number, it's invalid
29            if (eCount || j === index || j === length - 1) return false;
30            eCount++; // Increment exponent counter
31            // Skip the sign of the exponent part if it's there
32            if (s[j + 1] === '+' || s[j + 1] === '-') {
33                // Increments the index to skip the sign, then it checks if only a sign follows the exponent, it's invalid
34                if (++j === length - 1) return false;
35            }
36        } else if (!isDigit(s[j])) {
37            // If the character is not a digit, it's invalid
38            return false;
39        }
40    }
41    // If all conditions are met, it's a valid number
42    return true;
43}
44
45// Helper function to determine if a character is a digit
46function isDigit(char: string): boolean {
47    return char >= '0' && char <= '9';
48}
49
Not Sure What to Study? Take the 2-min Quiz：

Which of the following problems can be solved with backtracking (select multiple)

Time and Space Complexity

The given Python code snippet is designed to validate whether the input string s represents a valid number according to certain rules. To analyze its computational complexity, let's consider the size of the input string s, which is n.

Time Complexity

The function primarily utilizes a single while loop that traverses the input string s, which runs at most n times, where n is the length of the string.

  • Each check inside the loop (s[j] == '.', s[j] in 'eE', s[j].isnumeric(), etc.) can be considered to have a constant time complexity, i.e., O(1).
  • The while loop iterates over each character in the string once. The if checks within the loop do not contain any nested loops, and each condition is evaluated in constant time.

Thus, the overall time complexity of the function is O(n).

Space Complexity

  • The space complexity is mainly due to the variables i, j, dot, e, and the input string s. There are no data structures that grow with the input size.
  • The function uses a constant amount of extra space aside from the input string itself since no additional data structures such as lists or arrays are utilized to process the input.

Therefore, the space complexity of the function is O(1), indicating constant space usage.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫