65. Valid Number

Problem:

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.

Solution 1

You need to consider some edge case. After 5 times fail, the ugly code:

class Solution(object):
    def isNumber(self, s):
        """
        :type s: str
        :rtype: bool
        """
        s = s.strip().split('e')
        if not s[0]:
            return False
        if len(s) > 2:
            return False
        elif len(s) == 2:
            exp = s[1]
            if not exp:
                return False
            if exp[0] in '+-':
                exp = exp[1:]
            if not exp:
                return False
            for e in exp:
                if e.isdigit():
                    continue
                return False
        if s[0].strip() == '.':
            return False
        if s[0][0] in '+-':
            s[0] = s[0][1:]
        if not s[0]:
            return False
        decimal = s[0].split('.')
        if len(decimal) > 2:
            return False
        if not decimal[0] and not decimal[1]:
            return False
        for d in decimal:
            for c in d:
                if c.isdigit():
                    continue
                return False
        return True

Solution 2

Provided by @lanshan317

All valid number can be partitioned to 9 sections.

[spaces][sign1][digits1][.][digits2][e][sign2][digit3][spaces]

IF extra section appears, cut down.

IF missing, meet the following rules.

  • Must have at least digit1 and digit2
  • If contains e, must have digit3
  • If contains sign2, must have e

So first strip the string, and traverse the string to find out the sections. And judge whether the 3 rules is True. Any false will result in False. And at last to see whether the pointer has pointed to the last.

class Solution(object):
    def isNumber(self, s):
        """
        :type s: str
        :rtype: bool
        """
        s = s.strip()
        if len(s) == 0:
            return False
        
        hasE, hasDot, hasSign2 = False, False, False
        hasDigit1, hasDigit2, hasDigit3 = False, False, False
        i = 0
        
        if i < len(s) and s[i] in '+-':
            i += 1
        while i < len(s) and s[i].isdigit():
            i += 1
            hasDigit1 = True
        if i < len(s) and s[i] == '.':
            i += 1
            hasDot = True
        while i < len(s) and s[i].isdigit():
            i += 1
            hasDigit2 = True
        if i < len(s) and s[i] == 'e':
            i += 1
            hasE = True
        if i < len(s) and s[i] in '+-':
            i += 1
            hasSign2 = True
        while i < len(s) and s[i].isdigit():
            i += 1
            hasDigit3 = True

        if not hasDigit1 and not hasDigit2:
            return False
        if hasE and not hasDigit3:
            return False
        if hasSign2 and not hasE:
            return False

        return i == len(s)

Solution 3

Provided by @aynamron

Express the valid number by DFA.

DFA

In Solution2, we can separate the valid number into 9 sections. So, we can regard the 9 sections as 9 states.

DFA describe each state and it's transition. When a state gets a character, it will transit to next state or fail. And the valid number's end state must be 3, 5, 8 and 9.

Use a array to store the transition.

class Solution(object):
    def isNumber(self, s):
        """
        :type s: str
        :rtype: bool
        """
        states = [
            {'b': 0, 's': 1, 'd': 2, '.': 3},
            {'d': 2, '.': 3},
            {'b': 8, 'd': 2, '.': 4, 'e': 5},
            {'d': 4},
            {'b': 8, 'd': 4, 'e': 5},
            {'s': 6, 'd': 7},
            {'d': 7},
            {'b': 8, 'd': 7},
            {'b': 8}]
        currState = 0
        for c in s:
            if c.isdigit():
                state = 'd'
            elif c == ' ':
                state = 'b'
            elif c in "+-":
                state = 's'
            else:
                state = c
            if state not in states[currState].keys():
                return False
            currState = states[currState][state]
        if currState in [2, 4, 7, 8]:
            return True
        return False