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:
- 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'.'
.
Solutions
Solution 1: Case Discussion
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
orE
has appeared before, returnfalse
. Otherwise, we increment $dot$ by one; - If the current character is
e
orE
, ande
orE
has appeared before, or if the current character is at the beginning or end of the string, returnfalse
. 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, returnfalse
; - 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 |
|
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 |
|
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 |
|
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 |
|
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 |
|
1 2 3 4 5 6 7 8 9 |
|