博客

题解分析代码实现

实现一个函数用来判断字符串是否表示数值(包括整数和小数)。

题解分析

一个标识数字的字符串可能包括以下字符类型：

• 空格；

• 数组：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
    }
}