确定有限自动机 DFA

algorithm

在计算理论中，确定有限状态自动机或确定有限自动机（英语：deterministic finite automaton, DFA）是一个能实现状态转移的自动机。对于一个给定的属于该自动机的状态和一个属于该自动机字母表的字符，它都能根据事先给定的转移函数转移到下一个状态（这个状态可以是先前那个状态）。

以上是引用维基百科DFA的解释，DFA属于计算机理论，在上大学应该都有涉及到（实际上我都没印象了😅，理论课应该是有，只是当时完全听不懂，也没深入去研究）

最近在做leetcode题的时候，在题解中发现有人提到用DFA的思路去做，这才补了一下，对DFA有了一些了解

通俗点讲就是一个状态state1通过event转变为另外一个状态state2，而且这些state跟event是确定的，数量都是可以穷举的，主要是来解决这一类问题的。同样的也可以通过暴力解法，但是需要考虑特别多的情况，会有很多的if else，往往漏洞百出，无法覆盖所有的情况，这个时候DFA就显出它的优势了。

最开始是在做leetcode的这道题字符串转换整数 (atoi)的时候看题解有大佬提到DFA的，后来自己找了一道来练手有效数字，其实只是比字符串转整数的状态多了一些，稍微复杂一些，并且题目说明了陈诉的比较模糊，需要自己思考所有情况，所以在做的过程中有很多情况没有想到的以及跟测试用例想的不一样的，可以看到提交了很多次，后面的都是靠测试用例改进的

拿这道题来说，我们用DFA思想做的时候，首先要思考输入的字符都会有哪些情况，把这些转变为上面所说的event

  1. 空格 “ “
  2. 符号 “+” “-“ => sign
  3. 数字 0-9 => digit
  4. 点 “.” => dot
  5. “e” => e
  6. 其它 => other

我们可以设定几个状态

start 开始代表开始

sign 代表加入了符号

digit 代表加入数字

dot 代表加入小数点

e 代表指数

end 代表结束

这样我们就可以写出DFA表

space sign digit dot e other
start start sign digit dot end end
sign end end digit dot end end
digit end end digit digit e end
dot end end number end end end
e e sign digit end end end
end end end end end end end

实际上这不是第一版，自己没有考虑全所有的情况，导致最开始写的DFA表有些问题，后来都是看测试用例修改的，不用太纠结这个，考虑不全是很正常的，明白其中的道理就行

我们拿start这一行解释一下

如果碰见space，那么相当于还是start状态

+sign，就转变到sign状态，digit跟dot同理

e比较特殊了，在开始的时候是不可以跟e的，类似e15这样是错误的，所以直接end

其它行可以自己理解一下

最终的代码就是这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
func isNumber(s string) bool {
    s = strings.TrimSpace(s)
    m := make(map[string][]string)
    m["start"] = []string{"start", "sign", "digit", "dot", "end", "end"}
    m["sign"] = []string{"end", "end", "digit", "dot", "end", "end"}
    m["digit"] = []string{"end", "end", "digit", "digit", "e", "end"}
    m["dot"] = []string{"end", "end", "digit", "end", "end", "end"}
    m["e"] = []string{"e", "sign", "digit", "end", "end", "end"}
    m["end"] = []string{"end", "end", "end", "end", "end", "end"}

    state := "start"
    usePoint := 0
    useE := 0
    for i := range s {
        // 当前状态为digit的时候并且前面dot已经使用过，类似 6.5 这样数字后就不能再出现dot了，所以修改为end
        if state == "digit" && usePoint == 1 {
            m["digit"][3] = "end"
        }
        // 当前状态为digit的时候并且前面e已经使用过，类似 5e6 这样数字后就不能再出现e，并且不能再出现dot因为指数必须为整数，所以需要修改成end
        if state == "digit" && useE == 1 {
            m["digit"][3] = "end"
            m["digit"][4] = "end"
        }
        next := m[state][getChar(s[i])]
        state = next
        // 如果出现了"."以及"e"需要改变下状态
        if s[i] == '.' {
            usePoint = 1
        }
        if s[i] == 'e' {
            useE = 1
        }
    }
    // 最后的判断条件 状态必须是digit才是true
    return state == "digit"
}

// 对应我们上面说的6种event 对应map中字符串数组的下标0-5
func getChar(c byte) int {
    switch c {
    case ' ':
        return 0
    case '+', '-':
        return 1
    case '0', '1', '2', '3', '4', '5', '6', '7', '8', '9':
        return 2
    case '.':
        return 3
    case 'e':
        return 4
    default:
        return 5
    }
}

大家也可以自己去看题解

Comments