Leetcode 65: valid number

https://leetcode.com/problems/valid-number/

65. Valid Number

Total Accepted: 38767 Total Submissions: 328141 Difficulty: Hard

Validate if a given string is numeric.

Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true

Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.

Update (2015-02-10):
The signature of the C++ function had been updated. If you still see your function signature accepts a const char * argument, please click the reload button to reset your code definition.

Code

class Solution(object):
    def isNumber(self, s):
        s = s.strip()
        return self._isNumber(s, ["+", "-", "."], True, True)

    def _isNumber(self, s, valid_first_chars = [], check_dot=True, check_e=True):
        if not s: return False
        if s.isdigit(): return True

        if (not s[0] in map(str, range(10)) + valid_first_chars):
            return False

        if s[0] in valid_first_chars:
            if (s[0] == "+" or s[0] == "-") and self._isNumber(s[1:], ["."], check_dot, check_e):
                return True
            if s[0] == "." and self._isNumber(s[1:], [], False, check_e):
                return True
        
        if check_e:
            es = s.split("e")
            if len(es) > 2: return False
            if len(es)==2 and self._isNumber(es[0], ["+", "-", "."], True, False) \
                and self._isNumber(es[1], ["+", "-"], False, False):
                return True            

        if check_dot:
            dots = s.split(".")
            if len(dots) > 2: return False
            if len(dots)==2 and self._isNumber(dots[0], ["+", "-"], False, False) \
                and (self._isNumber(dots[1], [], False, False) or dots[1] == ''):
                return True 

        return False

Idea

My (also most people’s) way is going straight to handle different cases for parsing numbers.

The most trivial case: an empty string or a null variable can’t be a valid number (line 7)
Use string.isdigit() to check if a string contains pure number (without ‘+’, ‘-‘, ‘.’ or ‘e’). (line 8)
a valid number must start with 0~9 or “+”, “-” or “.” (line 10-11)
if `s` starts with “+” or “-“, then `s[1:]` should be a valid number without prefix as “+” or “-“. However `s[1:]` can start with `.`, for example, “+.43” is a valid number (line 14-15)
if `s` starts with “.”, then `s[1:]` should be a pure valid number without any possibility to have prefix such as “+”, “-” and “.” (line 16-17)
if you want to check if `s` is in scientific notation, the part before “e” should be a valid number with at most one prefix (“+”, “-” or “.”). The part after `e` can’t start with “.” but can start with “+” or “-“. (line 22-24)
if you want to check if `s` is in a float notation, the part before “.” should be a valid number without any dot in it. The part after “.” should not have any dot in it either. It should not have any sign (“+” or “-“) after “e”. (line 29-31)

Reference

An exhausted list of test case:

Leetcode 65: valid number

65. Valid Number

Leave a comment

Cancel reply