Skip to content

65. Valid Number

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:

  1. An integer number followed by an optional exponent.
  2. 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:

  1. Digits followed by a dot '.'.
  2. Digits followed by a dot '.' followed by digits.
  3. 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 '.'.

Solutions

Solution 1: Case Discussion

Thinking

A valid number has many shapes: an optional sign, an integer or decimal, then an optional exponent. \(n \le 20\), so a regex or a language parser would pass, but we must decide ourselves.

The bottleneck is how the rules cross: a decimal point cannot appear in the exponent, e needs digits on both sides, the exponent may have its own sign, and a lone . or + is illegal.

One left-to-right scan is enough: eat a leading sign, then count \(dot\) and \(e\) so each appears at most once, and reject as soon as a character or position is illegal. Linear time, constant extra space.

First, we check if the string starts with a positive or negative sign. If it does, we move the pointer \(i\) one step forward. If the pointer \(i\) has reached the end of the string at this point, it means the string only contains a positive or negative sign, so we return false.

If the character pointed to by the current pointer \(i\) is a decimal point, and there is no number after the decimal point, or if there is an e or E after the decimal point, we return false.

Next, we use two variables \(dot\) and \(e\) to record the number of decimal points and e or E respectively.

We use pointer \(j\) to point to the current character:

  • If the current character is a decimal point, and a decimal point or e or E has appeared before, return false. Otherwise, we increment \(dot\) by one;
  • If the current character is e or E, and e or E has appeared before, or if the current character is at the beginning or end of the string, return false. Otherwise, we increment \(e\) by one; then check if the next character is a positive or negative sign, if it is, move the pointer \(j\) one step forward. If the pointer \(j\) has reached the end of the string at this point, return false;
  • If the current character is not a number, return false.

After traversing the string, return true.

The time complexity is \(O(n)\), and the space complexity is \(O(1)\). Here, \(n\) is the length of the string.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def isNumber(self, s: str) -> bool:
        n = len(s)
        i = 0
        if s[i] in '+-':
            i += 1
        if i == n:
            return False
        if s[i] == '.' and (i + 1 == n or s[i + 1] in 'eE'):
            return False
        dot = e = 0
        j = i
        while j < n:
            if s[j] == '.':
                if e or dot:
                    return False
                dot += 1
            elif s[j] in 'eE':
                if e or j == i or j == n - 1:
                    return False
                e += 1
                if s[j + 1] in '+-':
                    j += 1
                    if j == n - 1:
                        return False
            elif not s[j].isnumeric():
                return False
            j += 1
        return True

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public boolean isNumber(String s) {
        int n = s.length();
        int i = 0;
        if (s.charAt(i) == '+' || s.charAt(i) == '-') {
            ++i;
        }
        if (i == n) {
            return false;
        }
        if (s.charAt(i) == '.'
            && (i + 1 == n || s.charAt(i + 1) == 'e' || s.charAt(i + 1) == 'E')) {
            return false;
        }
        int dot = 0, e = 0;
        for (int j = i; j < n; ++j) {
            if (s.charAt(j) == '.') {
                if (e > 0 || dot > 0) {
                    return false;
                }
                ++dot;
            } else if (s.charAt(j) == 'e' || s.charAt(j) == 'E') {
                if (e > 0 || j == i || j == n - 1) {
                    return false;
                }
                ++e;
                if (s.charAt(j + 1) == '+' || s.charAt(j + 1) == '-') {
                    if (++j == n - 1) {
                        return false;
                    }
                }
            } else if (s.charAt(j) < '0' || s.charAt(j) > '9') {
                return false;
            }
        }
        return true;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    bool isNumber(string s) {
        int n = s.size();
        int i = 0;
        if (s[i] == '+' || s[i] == '-') ++i;
        if (i == n) return false;
        if (s[i] == '.' && (i + 1 == n || s[i + 1] == 'e' || s[i + 1] == 'E')) return false;
        int dot = 0, e = 0;
        for (int j = i; j < n; ++j) {
            if (s[j] == '.') {
                if (e || dot) return false;
                ++dot;
            } else if (s[j] == 'e' || s[j] == 'E') {
                if (e || j == i || j == n - 1) return false;
                ++e;
                if (s[j + 1] == '+' || s[j + 1] == '-') {
                    if (++j == n - 1) return false;
                }
            } else if (s[j] < '0' || s[j] > '9')
                return false;
        }
        return true;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
func isNumber(s string) bool {
    i, n := 0, len(s)
    if s[i] == '+' || s[i] == '-' {
        i++
    }
    if i == n {
        return false
    }
    if s[i] == '.' && (i+1 == n || s[i+1] == 'e' || s[i+1] == 'E') {
        return false
    }
    var dot, e int
    for j := i; j < n; j++ {
        if s[j] == '.' {
            if e > 0 || dot > 0 {
                return false
            }
            dot++
        } else if s[j] == 'e' || s[j] == 'E' {
            if e > 0 || j == i || j == n-1 {
                return false
            }
            e++
            if s[j+1] == '+' || s[j+1] == '-' {
                j++
                if j == n-1 {
                    return false
                }
            }
        } else if s[j] < '0' || s[j] > '9' {
            return false
        }
    }
    return true
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
impl Solution {
    pub fn is_number(s: String) -> bool {
        let mut i = 0;
        let n = s.len();

        if let Some(c) = s.chars().nth(i) {
            if c == '+' || c == '-' {
                i += 1;
                if i == n {
                    return false;
                }
            }
        }
        if let Some(x) = s.chars().nth(i) {
            if x == '.'
                && (i + 1 == n
                    || (if let Some(m) = s.chars().nth(i + 1) {
                        m == 'e' || m == 'E'
                    } else {
                        false
                    }))
            {
                return false;
            }
        }

        let mut dot = 0;
        let mut e = 0;
        let mut j = i;

        while j < n {
            if let Some(c) = s.chars().nth(j) {
                if c == '.' {
                    if e > 0 || dot > 0 {
                        return false;
                    }
                    dot += 1;
                } else if c == 'e' || c == 'E' {
                    if e > 0 || j == i || j == n - 1 {
                        return false;
                    }
                    e += 1;
                    if let Some(x) = s.chars().nth(j + 1) {
                        if x == '+' || x == '-' {
                            j += 1;
                            if j == n - 1 {
                                return false;
                            }
                        }
                    }
                } else if !c.is_ascii_digit() {
                    return false;
                }
            }
            j += 1;
        }

        true
    }
}

1
2
3
4
5
6
7
public class Solution {
    private readonly Regex _isNumber_Regex = new Regex(@"^\s*[+-]?(\d+(\.\d*)?|\.\d+)([Ee][+-]?\d+)?\s*$");

    public bool IsNumber(string s) {
        return _isNumber_Regex.IsMatch(s);
    }
}

Comments