This content originally appeared on DEV Community and was authored by seanpgallivan
This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.
Leetcode Problem #65 (Hard): Valid Number
Description:
(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)
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:
- At least one digit, followed by a dot
'.'.- At least one digit, followed by a dot
'.', followed by at least one digit.- A dot
'.', followed by at least one digit.An integer can be split up into these components (in order):
- (Optional) A sign character (either
'+'or'-').- At least one digit.
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, returntrueifsis a valid number.
Examples:
Example 1: Input: s = "0" Output: true
Example 2: Input: s = "e" Output: false
Example 3: Input: s = "." Output: false
Example 4: Input: s = ".1" Output: true
Constraints:
1 <= s.length <= 20sconsists of only English letters (both uppercase and lowercase), digits (0-9), plus'+', minus'-', or dot'.'.
Idea:
(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)
To solve this problem, we should 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)
Javascript Code:
(Jump to: Problem Description || Solution Idea)
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
};
Python Code:
(Jump to: Problem Description || Solution Idea)
class Solution:
def isNumber(self, S: str) -> bool:
num, exp, sign, dec = False, False, False, False
for c in S:
if c >= '0' and c <= '9': num = True
elif c == 'e' or c == 'E':
if exp or not num: return False
else: exp, num, sign, dec = True, False, False, False
elif c == '+' or c == '-':
if sign or num or dec: return False
else: sign = True
elif c == '.':
if dec or exp: return False
else: dec = True
else: return False
return num
Java Code:
(Jump to: Problem Description || Solution Idea)
class Solution {
public boolean isNumber(String S) {
boolean num = false, exp = false, sign = false, dec = false;
for (int i = 0; i < S.length(); i++) {
char c = S.charAt(i);
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;
}
}
C++ Code:
(Jump to: Problem Description || Solution Idea)
class Solution {
public:
bool isNumber(string S) {
bool num = false, exp = false, sign = false, dec = false;
for (auto c : 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;
}
};
This content originally appeared on DEV Community and was authored by seanpgallivan
seanpgallivan | Sciencx (2021-05-15T09:15:05+00:00) Solution: Valid Number. Retrieved from https://www.scien.cx/2021/05/15/solution-valid-number/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.