leetcode 第10题 正则表达式匹配
其实我并不太喜欢使用动态规划来实现正则，但我看解题大多人都在用动规，有一个大佬用了NFA但代码不是很适合新手看，所以写一个简单点的解题方法。
有穷自动机的核心就是状态转换图，以最简单的 abbc 匹配 ab*c 为例
上图虽然看着比较乱，但其实很好理解。图上的一个圈就是一个状态(State)，一个箭头就是一条路径(Path)，从起点开始， 把每个箭头当一条路线，字符串配置到哪个字符，就走哪条路径，一直走到最后，如果手里正好没有字符了，那就是配置成功了。反之，如果中途无路可走，或到终点手里还有字符，在或者走到一半手里字符没有了，就是配置失败。
当出现如 b* 这类状态时，那由于 b 可出现零次或多次，所以意味着，可以从 a 直接走到 c 即 b 出现零次，如果有 b 也可继续在 b 上绕圈，直到字符串中的 b 用完。
但有一种特殊情况，由于是NFA，即意味着不确定，这个不确定指的就是在从状态选择接下来的路径时，会出现无法确定走哪条，或是说有多条可以走。
举个例子： abcabc 匹配 .*abc 这个正则在配置第一个 a 字符时就会出现，是走 . 呢，还是走 a 呢。
这种情况就是不确定性。反之如果每个状态有且仅有一条确定的路径可走，则叫确定的有穷自动机(DFA)。
对于这种情况，通常就是都走一下试试了。。
实现一个可以击败 5% 的代码吧~
const EOF rune = 0
const ANY rune = '.'
type State struct {
C rune
Path map[rune][]*State
IsAccept bool
}
func NewNFA(p string) *State {
start := &State{}
curStates := []*State{start}
var preStates []*State
var repeatState *State // 保存 * 前面的字符，也就是需要重复的字符
for _, c := range p {
switch c {
case '*':
repeatState.AddPath(repeatState)
preStates, curStates = curStates, append(curStates, preStates...)
default:
newState := &State{C: c}
repeatState = newState
addPath(curStates, newState)
preStates, curStates = curStates, []*State{newState}
}
}
receiveState := &State{IsAccept: true}
addPath(curStates, receiveState)
return start
}
func addPath(states []*State, path *State) {
for _, s := range states {
s.AddPath(path)
}
}
func getNextChar(s []rune, index int) rune {
if index >= len(s) {
return EOF
}
return s[index]
}
func (s *State) AddPath(path *State) {
if s.Path == nil {
s.Path = map[rune][]*State{}
}
s.Path[path.C] = append(s.Path[path.C], path)
}
// 获取可走的路径
func (s *State) GetMovablePath(c rune) []*State {
movablePath := s.Path[c]
if anyPath, ok := s.Path[ANY]; c == EOF || !ok {
return movablePath
} else {
return append(movablePath, anyPath...)
}
}
func (s *State) Match(str string) bool {
return s.doMatch([]rune(str), 0)
}
func (s *State) doMatch(str []rune, index int) bool {
if s.IsAccept {
if index >= len(str) {
return true
} else {
return false
}
}
c := getNextChar(str, index)
movablePath := s.GetMovablePath(c)
for _, path := range movablePath {
result := path.doMatch(str, index+1)
if result {
return true
}
}
return false
}
func isMatch(s string, p string) bool {
return NewNFA(p).Match(s)
}