A simple solution in Python based on DFA


  • 60
    A

    I was asked in the interview of linkedIn, writing it directly can be extremely complicated, for there are many special cases we have to deal with, and the code I wrote was messy. Then I failed to pass the interview.

    Here's a clear solution. With DFA we can easily get our idea into shape and then debug, and the source code is clear and simple.

    class Solution(object):
      def isNumber(self, s):
          """
          :type s: str
          :rtype: bool
          """
          #define a DFA
          state = [{}, 
                  {'blank': 1, 'sign': 2, 'digit':3, '.':4}, 
                  {'digit':3, '.':4},
                  {'digit':3, '.':5, 'e':6, 'blank':9},
                  {'digit':5},
                  {'digit':5, 'e':6, 'blank':9},
                  {'sign':7, 'digit':8},
                  {'digit':8},
                  {'digit':8, 'blank':9},
                  {'blank':9}]
          currentState = 1
          for c in s:
              if c >= '0' and c <= '9':
                  c = 'digit'
              if c == ' ':
                  c = 'blank'
              if c in ['+', '-']:
                  c = 'sign'
              if c not in state[currentState].keys():
                  return False
              currentState = state[currentState][c]
          if currentState not in [3,5,8,9]:
              return False
          return True
    

    enter image description here


  • -2
    J

    So many cases...
    How about doing something really magic with python?

        try:
            float(s)
            return True
        except:
            return False

  • 6
    A

    in the interview, this is not what they want.


  • 0
    W

    Why not start from state 0? Seems waste one state.


  • 6
    E

    Very cool solution. I picked it apart and made it (overly) explicit:

    class Solution(object):
        def isNumber(self, s):
            """
            :type s: str
            :rtype: bool
            """
            #define DFA state transition tables
            states = [{},
                     # State (1) - initial state (scan ahead thru blanks)
                     {'blank': 1, 'sign': 2, 'digit':3, '.':4},
                     # State (2) - found sign (expect digit/dot)
                     {'digit':3, '.':4},
                     # State (3) - digit consumer (loop until non-digit)
                     {'digit':3, '.':5, 'e':6, 'blank':9},
                     # State (4) - found dot (only a digit is valid)
                     {'digit':5},
                     # State (5) - after dot (expect digits, e, or end of valid input)
                     {'digit':5, 'e':6, 'blank':9},
                     # State (6) - found 'e' (only a sign or digit valid)
                     {'sign':7, 'digit':8},
                     # State (7) - sign after 'e' (only digit)
                     {'digit':8},
                     # State (8) - digit after 'e' (expect digits or end of valid input) 
                     {'digit':8, 'blank':9},
                     # State (9) - Terminal state (fail if non-blank found)
                     {'blank':9}]
            currentState = 1
            for c in s:
                # If char c is of a known class set it to the class name
                if c in '0123456789':
                    c = 'digit'
                elif c in ' \t\n':
                    c = 'blank'
                elif c in '+-':
                    c = 'sign'
                # If char/class is not in our state transition table it is invalid input
                if c not in states[currentState]:
                    return False
                # State transition
                currentState = states[currentState][c]
            # The only valid terminal states are end on digit, after dot, digit after e, or white space after valid input    
            if currentState not in [3,5,8,9]:
                return False
            return True
    

  • 1
    5

    you are very funny, and python is very powerful! so python get 100 scores, and u get 0! lol


  • 0
    C

    OMG, Just Brilliant!


  • 0
    S

    So brilliant... Reading this post make me feel that I've forgot everything learnt from my digital circus course... especially the merging states part. I ended up with a long long code of over 10 states for this problem lol.


  • 0

    @shenggu is your Last Name Lu?


  • 0
    S

    @heqingy wo qu dou mei you kan dao ID...


  • 0
    J

    Cool. This picture is something like FSA.


  • 0
    Y

    something wrong. this dfa return wrong result when input is "0123"


  • 0

    @yearss For me, it returns True, which is correct for this problem.

    If you doubt whether "0123" is a valid number, check the definition of "number" in language such as C/C++, python


  • 0
    G

    Great idea, here is my implementation.

    class Solution(object):
        def isNumber(self, s):
            """
            :type s: str
            :rtype: bool
            """
            states = [
                {' ': 0, 'sign': 1, 'digit': 2, '.': 3},
                {'digit': 2, '.': 3},
                {'digit': 2, '.': 4, 'e': 5, ' ': 8},
                {'digit': 4},
                {'digit': 4, 'e': 5, ' ': 8},
                {'sign': 6, 'digit': 7},
                {'digit': 7},
                {'digit': 7, ' ': 8},
                {' ': 8}
            ]
            cur = 0
            for c in s:
                if c == '+' or c == '-':
                    c = 'sign'
                elif '0' <= c <= '9':
                    c = 'digit'
                if c not in states[cur].keys():
                    return False
                cur = states[cur][c]
            return cur in [2, 4, 7, 8]
    

  • 0
    H

    Is that possible that the string starts with "e"(eg, e-10)?


  • 0
    H

    In terms of q3-->q5 and q4-->5, I am confused that why q3 and q4 could point to same q5?


  • 0
    A

    @Henry456 It depends on the definition of "valid number". At least, in most popular languages, I don't see any valid number starting with 'e'


  • 0
    A

    @Henry456 why not? it's just a state transition graph.


  • 0
    H

    @aynamron can you make up a number consistent with both q3-->q5 and q4-->q5? I still cannot get it! Thanks!


  • 0
    A

    @Henry456 you'd better review how DFA works and what this graph means. There's no such a number that matches both parallel paths.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.