LeetCode - Valid Number
Problem statement
A valid number can be split up into these components (in order):
A decimal number or an integer.
(Optional) An 'e' or 'E', followed by an integer.
A decimal number can be split up into these components (in order):
(Optional) A sign character (either '+' or '-').
One of the following formats: One or more digits, followed by a dot '.'.
One or more digits, followed by a dot '.', followed by one or more digits.
A dot '.', followed by one or more digits.
An integer can be split up into these components (in order):
(Optional) A sign character (either '+' or '-').
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.
Problem statement taken from: https://leetcode.com/problems/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 '.'.
Explanation
In these kinds of problems, we should first check the invalid cases. We return false the moment we discover any invalid case. We must iterate over the string and run a few checks based on the current character. While iterating, we should keep track of whether the signs (`+` or -), the exponent e or decimal . has appeared before or not.
We need to ensure the below cases are handled in our code:
The characters in the string belong to the set {+, -, ., e, [0-9]}.
No
.comes aftereorE.A dot
.should be followed by a digit.The character
eshould be followed either by+,-, or a digit [0-9].Any other non-numeric character appearing.
Reaching the end of S without an active number.
No more than one exponent character
eorEor one sign or decimal in the string.
Let's check the algorithm.
Algorithm
- set number = false
exponent = false
sign = false
decimal = false
- loop for character in s
// check if the current char is a number, then set the number flag to true
- if c >= '0' && c <= '9'
- number = true
// if char is an exponent, then verify
// appeared twice or before any number
// return false
// else set exponent to true and all other variables to false
- else if c == 'e' || c == 'E'
- if exponent || !number
- return false
- else
- exponent = true, sign = false, number = false, decimal = false
- if end
// if char is a sign
// return false if sign appeared before
// return false if it appeared after any number
// return false if it appeared after a decimal .
// else
// set sign to true
- else if c == '+' || c == '-'
- if sign || number || decimal
- return false
- else
- sign = true
- if end
// if char is a decimal
// return false if decimal appeared before
// return false if appeared after an exponent
// else
// set decimal to true
// if char is any character apart from number, sign, exponent or decimal
// return false
- else
- return false
- for end
// if a number has not appeared in the string, the number flag will be false
// else it will be true
// We return the number as our answer
- return number
The time complexity of this approach is O(n). The space complexity is O(1).
Let's check our algorithm in C++, Golang, and JavaScript.
C++ solution
class Solution {
public:
bool isNumber(string s) {
bool number = false, exponent = false, sign = false, decimal = false;
for (auto c : s) {
if (c >= '0' && c <= '9')
number = true;
else if (c == 'e' || c == 'E')
if (exponent || !number)
return false;
else
exponent = true, sign = false, number = false, decimal = false;
else if (c == '+' || c == '-')
if (sign || number || decimal)
return false;
else
sign = true;
else if (c == '.')
if (decimal || exponent)
return false;
else
decimal = true;
else
return false;
}
return number;
}
};
Golang solution
func isNumber(s string) bool {
number, exponent, sign, decimal := false, false, false, false
for _, c := range s {
if c >= '0' && c <= '9' {
number = true
} else if c == 'e' || c == 'E' {
if exponent || !number {
return false
} else {
exponent = true
sign = false
number = false
decimal = false
}
} else if c == '+' || c == '-' {
if sign || number || decimal {
return false
} else {
sign = true
}
} else if c == '.' {
if decimal || exponent {
return false
} else {
decimal = true
}
} else {
return false
}
}
return number
}
JavaScript solution
var isNumber = function(s) {
let number = false, exponent = false, sign = false, decimal = false;
for (c of s) {
if (c >= '0' && c <= '9')
number = true;
else if (c == 'e' || c == 'E')
if (exponent || !number)
return false;
else
exponent = true, sign = false, number = false, decimal = false;
else if (c == '+' || c == '-')
if (sign || number || decimal)
return false;
else
sign = true;
else if (c == '.')
if (decimal || exponent)
return false;
else
decimal = true;
else
return false;
}
return number;
};
Let's dry-run our algorithm for few examples to see how the solution works.
Input: '-90E3'
Step 1: set number = false
exponent = false
sign = false
decimal = false
Step 2: loop for auto c in s
c = '-'
if c >= '0' && c <= '9'
false
else if c == 'e' || c == 'E'
false
else if c == '+' || c == '-'
true
if sign || number || decimal
false || false || false
else
sign = true
Step 3: loop for auto c in s
c = '9'
if c >= '0' && c <= '9'
true
number = true
Step 4: loop for auto c in s
c = '0'
if c >= '0' && c <= '9'
true
number = true
Step 5: loop for auto c in s
c = 'E'
if c >= '0' && c <= '9'
false
else if c == 'e' || c == 'E'
true
if exponent || !number
false || !true
false || false
false
else
exponent = true
sign = false
number = false
decimal = false
Step 6: loop for auto c in s
c = '3'
if c >= '0' && c <= '9'
true
number = true
Step 7: loop for auto c in s
String ends
loop exit
Step 8: return number
We return true.
Input: '99e2.5'
Step 1: set number = false
exponent = false
sign = false
decimal = false
Step 2: loop for auto c in s
c = '9'
if c >= '0' && c <= '9'
true
number = true
Step 3: loop for auto c in s
c = '9'
if c >= '0' && c <= '9'
true
number = true
Step 4: loop for auto c in s
c = 'e'
if c >= '0' && c <= '9'
false
else if c == 'e' || c == 'E'
true
if exponent || !number
false || !true
false || false
false
else
exponent = true
sign = false
number = false
decimal = false
Step 5: loop for auto c in s
c = '.'
if c >= '0' && c <= '9'
false
else if c == 'e' || c == 'E'
false
else if c == '+' || c == '-'
false
else if c == '.'
true
if decimal || exponent
false || true
true
return false
The decimal . appeared after the exponent e. We return the answer as false.