Swift Leetcode Series: Valid Number

Facebook Interview Question 👍 👍 👍

Valid Number (Leetcode 65) -

You checkout the full story on The Swift Nerd blog with the link above.

Problem Description

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

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

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

1. (Optional) A sign character (either '+' or '-').
2. One of the following formats:
3. At least one digit, followed by a dot '.'.
4. At least one digit, followed by a dot '.', followed by at least one digit.
5. 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.

Complexity Analysis

Time = O(N)

Space = O(1)

Thank you for reading. If you liked this article and found it useful, share and spread it like wildfire!

You can find me on TheSwiftNerd | LinkedIn | Github