題解分析代碼實現

實現一個函數用來判斷字符串是否表示數值(包括整數和小數)。

題解分析

一個標識數字的字符串可能包括以下字符類型：

• 空格；

• 數組：0~9；

• 正負號

• 小數點

• 冪符號：e/E；

為了解決此類問題，需要使用有限狀態自動機，字符串有如下狀態：

• 0：開始的空格；

• 1：冪符號前的正負號；

• 2：小數點前的數字；

• 3：小數點、小數點后的數字；

• 4：小數點前為空格時：小數點、小數點后的數字；

• 5：冪符號；

• 6：冪符號后的正負號；

• 7：冪符號后的數字；

• 8：結尾的空格；
  合法的結束狀態有：2、3、7、8。

狀態轉移如下圖所示：

復雜度分析：

• 時間：需要遍歷整個字符串的長度，且狀態轉移為O(1)，所以為O(N)；

• 空間：只需常數額外空間，所以為O(1)；

代碼實現

狀態使用字典列表表示，具體實現為：

func?isNumber(strNum?string)?bool?{
????state?:=?[]map[byte]int{
????????{'?':0,?'s':1,?'d':2,?'.':4},????//?0:?start?with?'blank'
????????{'d':2,?'.':4},??????????????????//?1:?'sign'?before?e
????????{'d':2,?'.':3,?'e':5,?'?':8},????//?2:?'digit'?before?'.'
????????{'d':3,?'e':5,?'?':8},???????????//?3:?'digit'?after?'.'
????????{'d':3},?????????????????????????//?4:?'digit'?after?'.'(‘blank’?before?'dot')
????????{'s':6,?'d':7},??????????????????//?5:?'e'
????????{'d':7},?????????????????????????//?6:?'sign'?after?'e'
????????{'d':7,?'?':8},??????????????????//?7:?'digit'?after?e
????????{'?':8},?????????????????????????//?8:?end?with?'blank'
????}

????index?:=?0
????var?key?byte
????for?_,ch?:=?range?strNum?{
????????if?ch>='0'?&&?ch?<=?'9'{
????????????key?=?'d'
????????}else?{
????????????switch?ch?{
????????????case?'+',?'-':
????????????????key?=?'s'
????????????case?'e',?'E':
????????????????key?=?'e'
????????????case?'.',?'?':
????????????????key?=?byte(ch)
????????????default:
????????????????key?=?'?'
????????????}
????????}

????????if?_,ok:=state[index][key];?!ok{
????????????return?false
????????}
????????index?=?state[index][key]
????}

????switch?index?{
????case?2,3,7,8:
????????return?true
????default:
????????return?false
????}
}