65. Valid Number – Leetcode Solutions

June 20, 2024

Table of Contents

Description:

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.

Examples:

Example 1:

Input: s = "0"

Output: true

Example 2:

Input: s = "e"

Output: false

Example 3:

Input: s = "."

Output: false

Solution in Python:

To determine if a given string s is a valid number according to the specified rules, we need to carefully parse and validate the string. We will implement the solution in Python using a state machine approach to handle different parts of the number (integer, decimal, exponent) and their respective constraints.

Steps to Solve the Problem:

Define the States:
- We’ll use different states to keep track of the parts of the number being processed: the sign, integer part, decimal part, and exponent part.
- A state machine will help in transitioning between these states based on the characters encountered.
Initialize Variables:
- Flags to check if certain parts (like digits, dot, exponent) have been seen.
- Iterate through each character of the string to validate it according to the rules.
Check Validity:
- Handle optional sign at the beginning.
- Validate digits before and after the decimal point.
- Handle the exponent part, ensuring it is followed by an integer.
Return the Result:
- At the end of parsing, check if the necessary parts (digits) have been encountered and return the result accordingly.

Python

class Solution:
    def isNumber(self, s: str) -> bool:
        # Define the states
        seen_digit = False
        seen_dot = False
        seen_exponent = False
        num_after_e = True  # To check if there is a number after the exponent
        
        # Iterate through each character in the string
        for i, char in enumerate(s):
            if char.isdigit():
                seen_digit = True
                num_after_e = True
            elif char in ['+', '-']:
                # Sign can only appear at the start or immediately after an 'e' or 'E'
                if i > 0 and s[i-1] not in ['e', 'E']:
                    return False
                # There must be something after the sign
                if i == len(s) - 1:
                    return False
            elif char == '.':
                # Dot can only appear once and cannot appear after an 'e' or 'E'
                if seen_dot or seen_exponent:
                    return False
                seen_dot = True
            elif char in ['e', 'E']:
                # Exponent can only appear once and must follow a digit
                if seen_exponent or not seen_digit:
                    return False
                seen_exponent = True
                num_after_e = False  # Need at least one digit after exponent
            else:
                # Any other character is invalid
                return False
        
        # At the end, ensure there was at least one digit and a valid exponent if it exists
        return seen_digit and num_after_e

Detailed Explanation:

Initialization:
- seen_digit is a flag indicating if a digit has been encountered.
- seen_dot is a flag indicating if a decimal point has been encountered.
- seen_exponent is a flag indicating if an exponent (‘e’ or ‘E’) has been encountered.
- num_after_e is a flag to ensure there are digits following an exponent.
Character Processing:
- If the character is a digit, set seen_digit to True and num_after_e to True (indicating valid numbers before and after exponent).
- If the character is a sign (‘+’ or ‘-‘), ensure it is at the correct position (either at the beginning or right after an exponent).
- If the character is a dot, ensure it appears only once and not after an exponent.
- If the character is an exponent, ensure it appears only once, follows a digit, and is followed by a valid number.
- Any other character makes the string invalid.
Final Validation:
- Ensure that there is at least one digit (seen_digit must be True).
- Ensure that if an exponent was encountered, there is a valid number following it (num_after_e must be True).

This approach ensures that all specified rules for a valid number are checked comprehensively.

Solution in Javascript:

JavaScript

/**
 * @param {string} s
 * @return {boolean}
 */
var isNumber = function(s) {
    // Define states for our finite state machine
    const STATE_INITIAL = 0;
    const STATE_SIGN = 1;
    const STATE_INTEGER = 2;
    const STATE_POINT = 3;
    const STATE_POINT_WITHOUT_INT = 4;
    const STATE_FRACTION = 5;
    const STATE_EXP = 6;
    const STATE_EXP_SIGN = 7;
    const STATE_EXP_NUMBER = 8;
    const STATE_END = 9;

    // Define the state transition table
    const transitions = [
        // STATE_INITIAL
        { ' ': STATE_INITIAL, 'sign': STATE_SIGN, 'digit': STATE_INTEGER, '.': STATE_POINT_WITHOUT_INT },
        // STATE_SIGN
        { 'digit': STATE_INTEGER, '.': STATE_POINT_WITHOUT_INT },
        // STATE_INTEGER
        { 'digit': STATE_INTEGER, '.': STATE_POINT, 'e': STATE_EXP, 'E': STATE_EXP, ' ': STATE_END },
        // STATE_POINT
        { 'digit': STATE_FRACTION, 'e': STATE_EXP, 'E': STATE_EXP, ' ': STATE_END },
        // STATE_POINT_WITHOUT_INT
        { 'digit': STATE_FRACTION },
        // STATE_FRACTION
        { 'digit': STATE_FRACTION, 'e': STATE_EXP, 'E': STATE_EXP, ' ': STATE_END },
        // STATE_EXP
        { 'sign': STATE_EXP_SIGN, 'digit': STATE_EXP_NUMBER },
        // STATE_EXP_SIGN
        { 'digit': STATE_EXP_NUMBER },
        // STATE_EXP_NUMBER
        { 'digit': STATE_EXP_NUMBER, ' ': STATE_END },
        // STATE_END
        { ' ': STATE_END },
    ];

    // Initialize the state to STATE_INITIAL
    let state = STATE_INITIAL;

    // Helper function to identify character type
    function charType(ch) {
        if ('0123456789'.includes(ch)) {
            return 'digit';
        } else if ('+-'.includes(ch)) {
            return 'sign';
        } else if ('eE'.includes(ch)) {
            return 'e';
        } else if (ch === '.') {
            return '.';
        } else if (ch === ' ') {
            return ' ';
        } else {
            return null;
        }
    }

    // Process each character in the input string
    for (let i = 0; i < s.length; i++) {
        let char = s[i];
        let type = charType(char);
        if (type === null || !transitions[state].hasOwnProperty(type)) {
            return false;
        }
        state = transitions[state][type];
    }

    // Check if the final state is valid
    return [STATE_INTEGER, STATE_POINT, STATE_FRACTION, STATE_EXP_NUMBER, STATE_END].includes(state);
};

Solution in Java:

Java

class Solution {
    public boolean isNumber(String s) {
        // Define states for our finite state machine
        final int STATE_INITIAL = 0;
        final int STATE_SIGN = 1;
        final int STATE_INTEGER = 2;
        final int STATE_POINT = 3;
        final int STATE_POINT_WITHOUT_INT = 4;
        final int STATE_FRACTION = 5;
        final int STATE_EXP = 6;
        final int STATE_EXP_SIGN = 7;
        final int STATE_EXP_NUMBER = 8;
        final int STATE_END = 9;

        // Define the state transition table
        int[][] transitions = new int[][]{
            // STATE_INITIAL
            {STATE_INITIAL, STATE_SIGN, STATE_INTEGER, STATE_POINT_WITHOUT_INT, -1, -1, -1, -1, -1, -1},
            // STATE_SIGN
            {-1, -1, STATE_INTEGER, STATE_POINT_WITHOUT_INT, -1, -1, -1, -1, -1, -1},
            // STATE_INTEGER
            {STATE_END, -1, STATE_INTEGER, STATE_POINT, STATE_EXP, -1, -1, -1, -1, -1},
            // STATE_POINT
            {STATE_END, -1, STATE_FRACTION, -1, STATE_EXP, -1, -1, -1, -1, -1},
            // STATE_POINT_WITHOUT_INT
            {-1, -1, STATE_FRACTION, -1, -1, -1, -1, -1, -1, -1},
            // STATE_FRACTION
            {STATE_END, -1, STATE_FRACTION, -1, STATE_EXP, -1, -1, -1, -1, -1},
            // STATE_EXP
            {-1, STATE_EXP_SIGN, STATE_EXP_NUMBER, -1, -1, -1, -1, -1, -1, -1},
            // STATE_EXP_SIGN
            {-1, -1, STATE_EXP_NUMBER, -1, -1, -1, -1, -1, -1, -1},
            // STATE_EXP_NUMBER
            {STATE_END, -1, STATE_EXP_NUMBER, -1, -1, -1, -1, -1, -1, -1},
            // STATE_END
            {STATE_END, -1, -1, -1, -1, -1, -1, -1, -1, -1},
        };

        // Initialize the state to STATE_INITIAL
        int state = STATE_INITIAL;

        // Process each character in the input string
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            int type = charType(ch);
            if (type == -1 || transitions[state][type] == -1) {
                return false;
            }
            state = transitions[state][type];
        }

        // Check if the final state is valid
        return state == STATE_INTEGER || state == STATE_POINT || state == STATE_FRACTION || state == STATE_EXP_NUMBER || state == STATE_END;
    }

    // Helper function to identify character type
    private int charType(char ch) {
        if (ch >= '0' && ch <= '9') {
            return 2; // digit
        } else if (ch == '+' || ch == '-') {
            return 1; // sign
        } else if (ch == 'e' || ch == 'E') {
            return 4; // exponent
        } else if (ch == '.') {
            return 3; // dot
        } else if (ch == ' ') {
            return 0; // space
        } else {
            return -1; // invalid character
        }
    }
}

Solution in C#:

C#

public class Solution {
    public bool IsNumber(string s) {
        // Define states for our finite state machine
        const int STATE_INITIAL = 0;
        const int STATE_SIGN = 1;
        const int STATE_INTEGER = 2;
        const int STATE_POINT = 3;
        const int STATE_POINT_WITHOUT_INT = 4;
        const int STATE_FRACTION = 5;
        const int STATE_EXP = 6;
        const int STATE_EXP_SIGN = 7;
        const int STATE_EXP_NUMBER = 8;
        const int STATE_END = 9;

        // Define the state transition table
        int[][] transitions = new int[][] {
            // STATE_INITIAL
            new int[] { STATE_INITIAL, STATE_SIGN, STATE_INTEGER, STATE_POINT_WITHOUT_INT, -1, -1, -1, -1, -1, -1 },
            // STATE_SIGN
            new int[] { -1, -1, STATE_INTEGER, STATE_POINT_WITHOUT_INT, -1, -1, -1, -1, -1, -1 },
            // STATE_INTEGER
            new int[] { STATE_END, -1, STATE_INTEGER, STATE_POINT, STATE_EXP, -1, -1, -1, -1, -1 },
            // STATE_POINT
            new int[] { STATE_END, -1, STATE_FRACTION, -1, STATE_EXP, -1, -1, -1, -1, -1 },
            // STATE_POINT_WITHOUT_INT
            new int[] { -1, -1, STATE_FRACTION, -1, -1, -1, -1, -1, -1, -1 },
            // STATE_FRACTION
            new int[] { STATE_END, -1, STATE_FRACTION, -1, STATE_EXP, -1, -1, -1, -1, -1 },
            // STATE_EXP
            new int[] { -1, STATE_EXP_SIGN, STATE_EXP_NUMBER, -1, -1, -1, -1, -1, -1, -1 },
            // STATE_EXP_SIGN
            new int[] { -1, -1, STATE_EXP_NUMBER, -1, -1, -1, -1, -1, -1, -1 },
            // STATE_EXP_NUMBER
            new int[] { STATE_END, -1, STATE_EXP_NUMBER, -1, -1, -1, -1, -1, -1, -1 },
            // STATE_END
            new int[] { STATE_END, -1, -1, -1, -1, -1, -1, -1, -1, -1 }
        };

        // Initialize the state to STATE_INITIAL
        int state = STATE_INITIAL;

        // Process each character in the input string
        for (int i = 0; i < s.Length; i++) {
            char ch = s[i];
            int type = CharType(ch);
            if (type == -1 || transitions[state][type] == -1) {
                return false;
            }
            state = transitions[state][type];
        }

        // Check if the final state is valid
        return state == STATE_INTEGER || state == STATE_POINT || state == STATE_FRACTION || state == STATE_EXP_NUMBER || state == STATE_END;
    }

    // Helper function to identify character type
    private int CharType(char ch) {
        if (ch >= '0' && ch <= '9') {
            return 2; // digit
        } else if (ch == '+' || ch == '-') {
            return 1; // sign
        } else if (ch == 'e' || ch == 'E') {
            return 4; // exponent
        } else if (ch == '.') {
            return 3; // dot
        } else if (ch == ' ') {
            return 0; // space
        } else {
            return -1; // invalid character
        }
    }
}

65. Valid Number – Leetcode Solutions

Description:

Solution in Python:

Solution in Javascript:

Solution in Java:

Solution in C#:

Popular

297. Serialize and Deserialize Binary Tree – Leetcode Solutions

352. Data Stream as Disjoint Intervals – Leetcode Solutions

165. Compare Version Numbers – Leetcode Solutions

99. Recover Binary Search Tree – Leetcode Solutions

347. Top K Frequent Elements – Leetcode Solutions

315. Count of Smaller Numbers After Self – Leetcode Solutions

42. Trapping Rain Water – Leetcode Solutions

65. Valid Number – Leetcode Solutions

Description:

Solution in Python:

Solution in Javascript:

Solution in Java:

Solution in C#:

Related Post

Popular