Valid Number (Leetcode 65)

Difficulty: Hard Link : Day 15: May Leetcode Challenge Asked in : Facebook, Linkedin, Twitch

Problem Description

valid number can be split up into these components (in order):

  1. decimal number or an integer.
  2. (Optional) An 'e' or 'E', followed by an integer.

decimal number can be split up into these components (in order):

  1. (Optional) A sign character (either '+' or '-').
  2. One of the following formats:
    1. At least one digit, followed by a dot '.'.
    2. At least one digit, followed by a dot '.', followed by at least one digit.
    3. A dot '.', followed by at least one digit.

An integer can be split up into these components (in order):

  1. (Optional) A sign character (either '+' or '-').
  2. 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, return true if s is a valid number.

Examples

Input: s = "0"
Output: true
Input: s = "e"
Output: false
Input: s = "."
Output: false
Input: s = ".1"
Output: true

Constraints

  • 1 <= s.length <= 20
  • s consists of only English letters (both uppercase and lowercase), digits (0-9), plus '+', minus '-', or dot '.'.

Solution

The description looks very tricky and can be difficult to come up with initial solution. The problem is a Hard level problem not because of the logic but due to the edge cases and conditions. You can imagine this problem as an advanced level fizzbuzz problem (literally!). I would recommend going through the examples of valid and non-valid numbers and reason why lie on that category. After going through the examples you can come up with a list of rules that your number should follow.

The way you should approach the problem is start with writing a list of rules you need to check. If any character fails to follow the rules then we should return false immediately. We can traverse every element and connect our cases with if-else as only one of the case would be valid. The following are the rules you should check:-

  1. The “e”/ “E” should not come before we have seen any number (like “e123”). Also ‘e’/ ‘E’ should not occur more than once.
  2. There should be at least 1 numeric value in the entire string.
  3. Any character other than ‘e’/’E’ is not accepted.
  4. The decimal “.” should not occur more than once, also it should not occur after we have seen an exponent (e/E).
  5. The sign (+/-) can either occur at 0th index or immediately after exponent (e/E). All other occurrences are invalid.

All other instances are invalid and we can return false directly. To make our work easy, we have taken three flags (boolean) for checking if a Numeric, Decimal or Exponent has already been seen. We would be checking all the above rules and updating the flags.

Code

Swift

class Solution {
func isNumber(_ s: String) -> Bool {
var isNum = false
var isDecimal = false
var isExp = false
var arr = Array(s)
for (index,elem) in arr.enumerated() {
if elem >= "0" , elem <= "9" {
isNum = true
}
else if "+-".contains(elem) {
if index != 0 , arr[index 1].lowercased() != "e" {
return false
}
}
else if elem == "." {
if isDecimal || isExp {
return false
}
isDecimal = true
}
else if elem.lowercased() == "e"{
if isExp || isNum == false {
return false
}
isNum = false
isExp = true
}
else{
return false
}
}
return isNum
}
}
view raw valid_number.swift hosted with ❤ by GitHub

Python

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
view raw valid_number.py hosted with ❤ by GitHub

Java

class Solution {
public boolean isNumber(String s) {
s = s.trim();
boolean pointPresent = false;
boolean ePresent = false;
boolean numberPresent = false;
boolean numberAfterE = true;
for(int i=0; i<s.length(); i++) {
if('0' <= s.charAt(i) && s.charAt(i) <= '9') {
numberPresent = true;
numberAfterE = true;
} else if(s.charAt(i) == '.') {
if(ePresent || pointPresent) {
return false;
}
pointPresent = true;
} else if(s.charAt(i) == 'e' || s.charAt(i) =='E') {
if(ePresent || !numberPresent) {
return false;
}
numberAfterE = false;
ePresent = true;
} else if(s.charAt(i) == '' || s.charAt(i) == '+') {
if(i != 0 && s.charAt(i1) != 'e') {
return false;
}
} else {
return false;
}
}
return numberPresent && numberAfterE;
}
}
view raw valid_number.java hosted with ❤ by GitHub

Complexity Analysis

Time = O(N)

Space = O(1)

Leave a Reply

Your email address will not be published. Required fields are marked *