LeetCode 10 正则表达式匹配 Regular Expression Matching

by acdzh · 2020年4月3日20:2 · 68 WORDS · ~ 1 mins reading time · 0 Visitors |

这个题本来没什么好说的, 简单的动态规划.

本来想直接糊个动态规划过去..然后看到题解里一个有限自动机的解法. 不过感觉废话挺多, 有些写法有些复杂, 比如下面这部分

type Node struct {
    C        byte
    Parent   *Node
    Children map[byte][]*Node
    End      bool
    Size     int
}

func (n *Node) Append(c byte, child *Node) {
    m := n.Children
    if m == nil {
        m = make(map[byte][]*Node)
        n.Children = m
    }
    list := m[c]
    if list == nil {
        list = make([]*Node, 0)
    }
    for _, v := range list {
        if v == child {
            m[c] = list
            return
        }
    }
    list = append(list, child)
    m[c] = list
}

作者：qianjigui
链接：https://leetcode-cn.com/problems/regular-expression-matching/solution/yi-bu-dao-wei-zhi-jie-an-zheng-ze-biao-da-shi-de-s/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

有些迷惑..明明一句就好了, 实在不清楚为什么写这么多

type Node struct {
    C          byte
    isEnd      bool
    router     map[byte]([]*Node)
    parentNode []*Node
    canBack    bool
}

func (node *Node) appendRouter(c byte, next *Node) {
    node.router[c] = append(node.router[c], next)
}

我的编译原理当年就没好好学...年代久远, 折腾一阵子, 最后总算用了80行实现了下面这堆垃圾:

type Node struct {
    C          byte
    isEnd      bool
    router     map[byte]([]*Node)
    parentNode []*Node
    canBack    bool
}

func (node *Node) appendRouter(c byte, next *Node) {
    node.router[c] = append(node.router[c], next)
}

func getDFA(p string) *Node {
    pLen := len(p)
    begin := Node{'>', true, make(map[byte]([]*Node)), []*Node{nil}, false}
    last := &begin
    for i := 0; i < pLen; i++ {
        if p[i] == '.' {
            t := &Node{'.', true, make(map[byte]([]*Node)), []*Node{last}, false}
            last.appendRouter('.', t)
            last.isEnd = false
            if last.canBack {
                for _, pp := range last.parentNode {
                    pp.appendRouter('.', t)
                    t.parentNode = append(t.parentNode, pp)
                }
            }
            last = t
        } else if p[i] == '*' {
            last.canBack = true
            last.appendRouter(last.C, last)
            if i == pLen-1 {
                for _, p := range last.parentNode {
                    p.isEnd = true
                }
            }
        } else {
            t := &Node{p[i], true, make(map[byte]([]*Node)), []*Node{last}, false}
            last.appendRouter(p[i], t)
            last.isEnd = false
            if last.canBack {
                for _, pp := range last.parentNode {
                    pp.appendRouter(p[i], t)
                    t.parentNode = append(t.parentNode, pp)
                }
            }
            last = t
        }
    }
    return &begin
}

func check(p *Node, s string, i int) bool {
    if i > len(s) {
        return false
    }

    if i == len(s) {
        if p.isEnd {
            return true
        } else {
            return false
        }
    }

    for k, v := range p.router {
        if k != s[i] && k != '.' {
            continue
        }
        for _, vv := range v {
            if check(vv, s, i+1) {
                return true
            }
        }
    }
    return false
}

func isMatch(s string, p string) bool {
    return check(getDFA(p), s, 0)
}