LC 0065 [H] Valid Number - ALawliet/algorithms GitHub Wiki

this problem just sucks with too many edge cases, need to just memorize

"459277e38+" false
"3." true
"." false
"0e" false

We use three flags: met_dot, met_e, met_digit, mark if we have met ., e or any digit so far. First we strip the string, then go through each char and make sure:

• If char is + or -, then prev char (if there is one) must be e
• . cannot appear twice or after e
• e cannot appear twice, and there must be at least one digit before and after e
• All other non-digit char is invalid

---

'e' or 'E'

class Solution:
    def isNumber(self, s: str) -> bool:
        dot = e = digit = False # store the last previously met

        for i, x in enumerate(s):
            # check the for 'e' types
            if x == 'E': x = x.lower()

            if x in '+-':
                if i > 0 and s[i-1] != 'e': return False # sign must come right after e, must be like 'e+7', 'e-1', so need to check [i-1]

            elif x == '.' : # not dot and not e
                if dot or e: return False # digit must come before ., can't be consec '..' or after 'e.'
                dot = True
                # e = False # not needed, but makes sense

            elif x == 'e': # not e and digit
                if e or not digit: return False # can't be like consec 'ee', must be like '1e'
                e = True # set next e
                digit = False # consume prev digit like '0e'

            # if we get past here it must either be a digit or not

            elif x.isdigit():
                digit = True

            else:
                return False

        return digit

class Solution(object):
    def isNumber(self, s):
        """
        :type s: str
        :rtype: bool
        """
        s = s.strip()

        met_dot = met_e = met_digit = False

        for i, char in enumerate(s):
            # If char is + or -, then prev char (if there is one) must be e
            if char in ['+', '-']:
                if i > 0 and s[i-1].lower() != 'e':
                    return False

            # . cannot appear twice or after e
            elif char == '.':
                if met_dot or met_e:
                    return False
                met_dot = True

            # e cannot appear twice, and there must be at least one digit before and after e
            elif char.lower() == 'e':
                if met_e or not met_digit:
                    return False
                met_e = True
                met_digit = False

            elif char.isdigit():
                met_digit = True

            # All other non-digit char is invalid
            elif not char.isdigit():
                return False

        # digit must come after e, can't end in e
        return met_digit

---

DFA = deterministic finite automaton

class Solution(object):
  def isNumber(self, s):
      """
      :type s: str
      :rtype: bool
      """
      #define a DFA
      state = [{}, # 0
              {'blank': 1, 'sign': 2, 'digit':3, '.':4}, #q1
              {'digit':3, '.':4}, #q2
              {'digit':3, '.':5, 'e':6, 'blank':9}, #q3
              {'digit':5}, #q4
              {'digit':5, 'e':6, 'blank':9}, #q5
              {'sign':7, 'digit':8}, #q6
              {'digit':8}, #q7
              {'digit':8, 'blank':9}, #q8
              {'blank':9}] #q9

      q = 1 # current state

      for c in s:
          if '0' <= c <= '9':
              c = 'digit'
          elif c == ' ':
              c = 'blank'
          elif c in ['+','-']:
              c = 'sign'

          if c not in state[q].keys(): # no next state
              return False

          q = state[q][c]

      if q not in [3,5,8,9]: # ending states with 2 circles
          return False

      return True

        #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}]