该题解使用了有限状态自动机(Finite State Machine, FSM)的方法来解决问题。首先,定义了不同的状态(State)和字符类型(CharType)。然后,根据题目给出的有效数字的定义,构建了状态转移图,其中包含了各个状态下对应字符类型的下一个状态。最后,遍历输入字符串,根据当前字符的类型和当前状态,进行状态转移,如果遇到非法字符或者无法转移的状态,则返回false。最终,如果字符串遍历完成后,状态机处于接受状态(即整数、小数、指数部分的数字、或者末尾空格状态),则返回true,表示字符串是一个有效数字。
时间复杂度: O(n)
空间复杂度: O(1)
from enum import Enum, auto
class Solution:
def isNumber(self, s: str) -> bool:
class State(Enum):
STATE_INITIAL = auto()
STATE_INT_SIGN = auto()
STATE_INTEGER = auto()
STATE_POINT = auto()
STATE_POINT_WITHOUT_INT = auto()
STATE_FRACTION = auto()
STATE_EXP = auto()
STATE_EXP_SIGN = auto()
STATE_EXP_NUMBER = auto()
STATE_END = auto()
class CharType(Enum):
CHAR_NUMBER = auto()
CHAR_EXP = auto()
CHAR_POINT = auto()
CHAR_SIGN = auto()
CHAR_SPACE = auto()
CHAR_ILLEGAL = auto()
def toCharType(ch):
if ch.isdigit():
return CharType.CHAR_NUMBER
elif ch.lower() == 'e':
return CharType.CHAR_EXP
elif ch == '.':
return CharType.CHAR_POINT
elif ch == '+' or ch == '-':
return CharType.CHAR_SIGN
elif ch == ' ':
return CharType.CHAR_SPACE
else:
return CharType.CHAR_ILLEGAL
transfer = {
State.STATE_INITIAL: {
CharType.CHAR_SPACE: State.STATE_INITIAL,
CharType.CHAR_NUMBER: State.STATE_INTEGER,
CharType.CHAR_POINT: State.STATE_POINT_WITHOUT_INT,
CharType.CHAR_SIGN: State.STATE_INT_SIGN,
},
State.STATE_INT_SIGN: {
CharType.CHAR_NUMBER: State.STATE_INTEGER,
CharType.CHAR_POINT: State.STATE_POINT_WITHOUT_INT,
},
State.STATE_INTEGER: {
CharType.CHAR_NUMBER: State.STATE_INTEGER,
CharType.CHAR_EXP: State.STATE_EXP,
CharType.CHAR_POINT: State.STATE_POINT,
CharType.CHAR_SPACE: State.STATE_END,
},
State.STATE_POINT: {
CharType.CHAR_NUMBER: State.STATE_FRACTION,
CharType.CHAR_EXP: State.STATE_EXP,
CharType.CHAR_SPACE: State.STATE_END,
},
State.STATE_POINT_WITHOUT_INT: {
CharType.CHAR_NUMBER: State.STATE_FRACTION,
},
State.STATE_FRACTION: {
CharType.CHAR_NUMBER: State.STATE_FRACTION,
CharType.CHAR_EXP: State.STATE_EXP,
CharType.CHAR_SPACE: State.STATE_END,
},
State.STATE_EXP: {
CharType.CHAR_NUMBER: State.STATE_EXP_NUMBER,
CharType.CHAR_SIGN: State.STATE_EXP_SIGN,
},
State.STATE_EXP_SIGN: {
CharType.CHAR_NUMBER: State.STATE_EXP_NUMBER,
},
State.STATE_EXP_NUMBER: {
CharType.CHAR_NUMBER: State.STATE_EXP_NUMBER,
CharType.CHAR_SPACE: State.STATE_END,
},
State.STATE_END: {
CharType.CHAR_SPACE: State.STATE_END,
},
}
st = State.STATE_INITIAL
for ch in s:
char_type = toCharType(ch)
if char_type not in transfer[st]:
return False
st = transfer[st][char_type]
return st in [State.STATE_INTEGER, State.STATE_POINT, State.STATE_FRACTION,
State.STATE_EXP_NUMBER, State.STATE_END]