Valid Number

LeetCode 65 | Difficulty: Hard

Hard

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

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

Topics: String

---

Approach

String Processing

Consider character frequency counts, two-pointer approaches, or building strings efficiently. For pattern matching, think about KMP or rolling hash. For palindromes, expand from center or use DP.

When to use

Anagram detection, palindrome checking, string transformation, pattern matching.

---

Solutions

Solution 1: C# (Best: 88 ms)

Metric	Value
Runtime	88 ms
Memory	N/A
Date	2018-07-02

Solution

public class Solution {
    public bool IsNumber(string s) {
       s = s.Trim();
    if (string.IsNullOrEmpty(s)) return false;
    if (s.IndexOf('e') != s.LastIndexOf('e')) return false;
    int i = 0;
    var index = s.IndexOf('e');
    if (index != -1)
    { //scientific notation {real number}e{integer}

        //check if e is the last character
        if (index == s.Length - 1) return false;
        return IsValidDecimal(s.Substring(i, index - i))
            && IsValidInteger(s.Substring(index + 1));
    }
    else
    {
        return IsValidDecimal(s.Substring(i, s.Length - i));
    }
}
public bool IsValidDecimal(string s)
{
    bool isAtleastOneNumber = false;
    if (string.IsNullOrEmpty(s)) return false;
    bool isDecimalEncountered = false;
    int i = 0;
    if (s[i] == '+' || s[i] == '-') i++;
    while (i < s.Length)
    {
        if (!isDecimalEncountered && s[i] == '.')
        {
            isDecimalEncountered = true;
            i++;
            continue;
        }
        if (!char.IsNumber(s[i]))
        {
            return false;
        }
        if (!isAtleastOneNumber)
        {
            isAtleastOneNumber = true;
        }
        i++;
    }
    return isAtleastOneNumber;
}

public bool IsValidInteger(string s)
{
    bool isAtleastOneNumber = false;
    if (string.IsNullOrEmpty(s)) return false;
    int i = 0;
    if (s[i] == '+' || s[i] == '-') i++;
    for (; i < s.Length; i++)
    {
        if (!isAtleastOneNumber) { isAtleastOneNumber = true; }
        if (!char.IsNumber(s[i])) return false;
    }
    return isAtleastOneNumber;
}
}

📜 1 more C# submission(s)

Submission (2018-07-02) — 88 ms, N/A

public class Solution {
    public bool IsNumber(string s) {
       s = s.Trim();
    if (string.IsNullOrEmpty(s)) return false;
    if(s.IndexOf('e') != s.LastIndexOf('e')) return false;
    int i = 0;
    if (s[0] == '+' || s[0] == '-')
        i++;
    var index = s.IndexOf('e');
    if(index!=-1)
    {
        if(index==s.Length-1) return false;
        return IsValidDecimal(s.Substring(i,index-i))   
                && IsValidInteger(s.Substring(index+1));
    }
    else return IsValidDecimal(s.Substring(i, s.Length-i));
}
public bool IsValidDecimal(string s)
{
    bool isAtleastOneNumber = false;
    if (string.IsNullOrEmpty(s)) return false;
    bool isDecimalEncountered = false;
    int i = 0;
    while (i < s.Length)
    {
        if(!isDecimalEncountered && s[i]=='.') { isDecimalEncountered = true; i++; continue;}
        if(!char.IsNumber(s[i])) return false;
        if(!isAtleastOneNumber) { isAtleastOneNumber = true;}
        i++;
    }
    return isAtleastOneNumber;
}

public bool IsValidInteger(string s)
{
    bool isAtleastOneNumber = false;
    if(string.IsNullOrEmpty(s)) return false;
    int i=0;
    if(s[i]=='+' || s[i]=='-') i++;
    for (; i < s.Length; i++)
    {
        if(!isAtleastOneNumber) { isAtleastOneNumber = true;}
        if(!char.IsNumber(s[i])) return false;
    }
    return isAtleastOneNumber;
}
}

---

Complexity Analysis

Approach	Time	Space
Solution	$O(n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Break the problem into smaller subproblems. Communicate your approach before coding.