劍指offer面試題20：表示數值的字元串（golang實作）

題目描述

請實作一個函數用來判斷字元串是否表示數值（包括整數和小數）。

數值（按順序）可以分成以下幾個部分：

1. 若幹空格
2. 一個 小數 或者 整數
3. （可選）一個 ‘e’ 或 ‘E’ ，後面跟着一個 整數
4. 若幹空格

小數（按順序）可以分成以下幾個部分：

1. （可選）一個符号字元（’+’ 或 ‘-’）
2. 下述格式之一：
   1. 至少一位數字，後面跟着一個點 ‘.’
   2. 至少一位數字，後面跟着一個點 ‘.’ ，後面再跟着至少一位數字
   3. 一個點 ‘.’ ，後面跟着至少一位數字

整數（按順序）可以分成以下幾個部分：

1. （可選）一個符号字元（’+’ 或 ‘-’）
2. 至少一位數字

部分數值列舉如下：

["+100", “5e2”, “-123”, “3.1416”, “-1E-16”, “0123”]

部分非數值列舉如下：

[“12e”, “1a3.14”, “1.2.3”, “±5”, “12e+5.4”]

示例1

輸入：s = "0"
輸出：true
           

示例2

輸入：s = "e"
輸出：false
           

示例3

輸入：s = "."
輸出：false
           

示例4

輸入：s = "    .1  "
輸出：true
           

Leetcode連結：劍指offer面試題20：表示數值的字元串

算法分析

本題采用有限狀态自動機，每次狀态轉移隻輸出true或者false，判斷目前狀态是接受狀态（以該狀态結尾是合法的）還是拒絕狀态（與接受狀态相反）。

• 确定狀态
  1. 起始的空格
  2. 符号位
  3. 整數部分
  4. 左側有整數的小數點
  5. 左側無整數的小數點
  6. 小數部分
  7. 幂符号 e \text{e} e 或 E \text{E} E
  8. 指數符号位
  9. 指數階數

  10. 末尾的空格

      易知，接受狀态為2、3、5、8、9，剩下的狀态為拒絕狀态

• 狀态轉移規則
  1. 當 c 為空格時，執行 t = ’ ’
  2. 當 c 為正負号時，執行 t = ‘s’ ;
  3. 當 c 為數字時，執行 t = ‘d’ ;
  4. 當 c 為 e \text{e} e， E \text{E} E 時，執行 t = ‘e’ ;
  5. 當 c 為 . 時，執行 t = ‘.’;
  6. 否則，執行 t = ‘?’ ，代表為不屬于判斷範圍的非法字元，後續直接傳回 falsefalse 。
• 複雜度分析
  1. 需要周遊字元串，是以時間複雜度為O(N)
  2. 額外的空間states與問題規模（字元串長度）無關，是以時間複雜度為O(1)
• 對比使用暴力枚舉的好處
  1. 減少if else, switch case的使用次數，代碼更加簡潔優雅
  2. 狀态表示直覺易讀，不易漏掉狀态
• 參考題解

Golang代碼如下

func isNumber(s string) bool {
	var states = []map[rune]int{
		map[rune]int{ ' ': 0, 's': 1, 'd': 2, '.': 4},	//	0
		map[rune]int{ 'd': 2, '.': 4 },					//	1
		map[rune]int{ 'd': 2, '.': 3, 'e': 6, ' ': 9 },	//	2
		map[rune]int{ 'd': 5, ' ': 9, 'e': 6 },			//	3
		map[rune]int{ 'd': 5 },							//	4
		map[rune]int{ 'd': 5, 'e': 6, ' ': 9 },			//	5
		map[rune]int{ 's': 7, 'd': 8 },					//	6
		map[rune]int{ 'd': 8 },							//	7
		map[rune]int{ 'd': 8, ' ': 9 },					//	8
		map[rune]int{ ' ': 9 },							//	9
	}

	state := 0
	var t rune
	for _, v := range s {
		if v == ' ' {
			t = ' '
		} else if v == '+' || v == '-' {
			t = 's'
		} else if v >= '0' && v <= '9' {
			t = 'd'
		} else if v == '.' {
			t = '.'
		} else if v == 'e' || v == 'E' {
			t = 'e'
		} else {
			t = '?'
		}
		if _, ok := states[state][t]; !ok {
			return false
		}
		state = states[state][t]
	}
	return state == 2 || state == 3 || state == 5 || state == 8 || state == 9
}