65. Valid Number

Valid Number

Problem Description

A valid number can be split up into these components (in order):

1. A decimal number or an integer.
2. (Optional) An 'e' or 'E', followed by an integer.

A decimal number can be split up into these components (in order):

1. (Optional) A sign character (either '+' or '-').
2. One of the following formats:
   1. One or more digits, followed by a dot '.'.
   2. One or more digits, followed by a dot '.', followed by one or more digits.
   3. A dot '.', followed by one or more digits.

An integer can be split up into these components (in order):

1. (Optional) A sign character (either '+' or '-').
2. One or more digits.

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"].

Given a string s, return true if s is a valid number.

 

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 '.'.

Approach) Character Conditional Solution

To solve this problem, we should just make a list of the possible error conditions and then check for each one.

The error conditions are:

• More than one exponent character ('e'/'E'), or seeing an 'e'/'E' when a number has not yet been seen.
• More than one sign, or a sign appearing after a decimal or number have been seen. This gets reset when passing an 'e'/'E'.
• More than one decimal, or a decimal appearing after an 'e'/'E' has been seen.
• Any other non-number character appearing.
• Reaching the end of S without an active number.

To help with this process, we can set up some boolean flags for the different things of which we're keeping track (num, exp, sign, dec). We'll also need to remember to reset all flags except exp when we find an 'e'/'E', as we're starting a new integer expression.

• Time Complexity: O(N) where N is the number of characters in S
• Space Complexity: O(1)
  
  

var isNumber = function(S) {
    let exp = false, sign = false, num = false, dec = false
    for (let c of S)
        if (c >= '0' && c <= '9') num = true     
        else if (c === 'e' || c === 'E')
            if (exp || !num) return false
            else exp = true, sign = false, num = false, dec = false
        else if (c === '+' || c === '-')
            if (sign || num || dec) return false
            else sign = true
        else if (c === '.')
            if (dec || exp) return false
            else dec = true
        else return false
    return num
};

Approach) State Machine

// If you insist on using built-in functions, use this:
// One line in Javascript:
var isNumberOneLine = function(s) {
    return !isNaN(s) && s.trim() !== '';
}

// Otherwise, this question is about using state machine. 
// I don't take credit for this solution.
// I just convert it into Javascript and add the time and space complexity analysis.
/**
 * Solution from: https://leetcode.com/problems/valid-number/discuss/360781/Python-with-state-machine-36ms
 * Function checks if a string is a number string.
 * Time = O(n) because we iterate through the whole string and each time
 * we do O(1) operations.
 * Space = O(n) because at most we store the whole inputString of length n.
 * @param {string} s
 * @return {boolean}
 */
var isNumber = function(s) {
    const SM = new StateMachine();
    // Trim trailing spaces 
    // because including spaces makes the states become too complicated.
    const inputString = s.trim();
    let state = 'start';

    for (const char of inputString) {
        try {
            state = SM.states[state][SM.classify(char)];
        }
        catch(error) {
            return false;
        }
    }
    return state === 'integer' || state === 'frac' || state === 'exp_int';
};

class StateMachine {
    constructor() {
        // States store all transitions:
        this.states = {
            'start': {'sign':'int_sign', 'digit':'integer', 'dot':'point'},
            'int_sign': {'digit':'integer', 'dot':'point'},
            'integer': {'digit':'integer', 'dot':'frac', 'e':'exp'},
            'point': {'digit':'frac'},
            'frac': {'digit':'frac', 'e':'exp'},
            'exp': {'digit':'exp_int', 'sign':'exp_sign'},
            'exp_sign': {'digit':'exp_int'},
            'exp_int': {'digit':'exp_int'}
        }
    }

    /**
     * Helper method returns the class of a char.
     * @param {string} char 
     * @returns {string}
     */
    classify(char) {
        if (!isNaN(parseInt(char))) return 'digit';
        if (char === '.') return 'dot';
        if (char === '+' || char === '-') return 'sign';
        if (char === 'e') return 'e';
        // If doesn't hit any of the cases above:
        throw new Error();
    }
}

Approach) One Liner

var isNumber = function(s) {
    return (! isNaN(s) ) && ( s.trim() !== "" ) && (! s.includes("Infinity") )
};
Empty strings are being coerced as zero in JavaScript, that's why we need to check if the string is empty, and return the opposite of isNaN if it's not.
Another alternative could be using typeof s === "number", however this has more corner cases to check for like "e" and ".", so I would prefer the previous way.

Conclusion

That’s all folks! In this post, we solved LeetCode problem 65. Valid Number

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!