Regular Expression Matching的NFA解法

事情的缘由是,在LeetCode上遇到了这么一题:Regular Expression Matching,大体的意思是用要求我们构建能实现一个简单的带规则的字符串匹配。 其实题目的意思已经比较明白,就是希望我们能实现正则的简单功能。比如”.”代表所有的字符,”*”表示重复0到正无穷次。这道题可以用DP或者Trie树解决,并且效率也比较高,但是,因为最近正好写了脚本解释器,所以正好尝试用下有穷自动机来解题。 有穷自动机分为两种,一种是NFA,一种是DFA。两者之间的区别就在于构造的方式,对于NFA来说,输入一个字符,它对应的是一个状态集,而对于DFA,则是一个固定的状态。两者也可以互相转换。相比较而言,对于这种相对比较简单的规则索引,我比较倾向于使用NFA。 首先我们需要对其进行构建NFA结构。因为本题的规则相对比较简单。比如说”a*”这样的结构,我们可以构造出如下的NFA结构: 对于”a”这样的结构,我们可以构造如下的结构: 所以,我们定义Node,和Path两个类作为节点和状态转移的两个对象: class Node { String token; LinkedList<Path> paths; boolean isEnd; public Node(String token)…