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)…

毕业那点事

终于要毕业了。大学四年就这么过了。本来以为会做些什么事情,结果就是这么浑浑噩噩的过来了。七月份就要正式上班了。就趁着最后的一段轻松的日子好好休息下了。 本来以为答辩会很难,而且要把握分数,不能太差(小于60),也不能太好(大于90),同时也要过得去,这个分数我定义为85~89之间,所以让导师给了我88,防止后面的老师分数拉高到90+。可惜事与愿违,答辩过程中,分配的组里,质量普遍偏低,所以就算我故意在问题上放水,也无奈被拉高到了90分,进了二辩。但是,这个二辩也没什么好玩的,在向辅导员得知,即使不去二辩也不会影响之后的成绩只会放弃成为优秀论文的机会之后,我妥妥的放弃了二辩。主要有以下几点: 这东西不是我一个人做的,但是这一届就我一个人使用这个东西参加答辩。 这个东西,已经跑不起来了。在用它获得20000元之后,我们就将他废弃了。现在连一个实物都没有,只有曾经留下的视频。 最重要的,学校相关的事务在我这边的优先级已经相当有限,如果有其他的事情冲突,就会放弃学校的。很不巧,我当天需要去张家港参加会议。所以妥妥的放弃了。 更可笑的是,居然有学生会的同学找到我,希望给学弟学妹做一讲座。我这大学里,基本上都是在翘课中度过,为了不给学弟学妹一个坏榜样,就不去了。 前几天终于知道自己双证的初审通过了。心里的大石头终于落地了。上学期因为实习的事情,然后挂了一科,也是错误的信任了一些人把。所以这学期还是靠自己,辞了实习,好好为自己的学位和毕业证努力,可惜翘课陋习难改。这学期又有一门课在考试提交作业的时候翘了。找了辅导员,教务处,行政处,对外联系人员,终于找到了那个老师的邮箱,然后把作业补交了。但是一直没有回信,因为听说不交作业,这部分分数50%,所以一直很担心这门课跪了,结果还好。通过了。这也是昨天才知道的。心里的石头落地了。 然后就是,我以为自己可以多线作战,一方面,实习的公司的事情;一方面,自己的私活;一方面,算法相关的训练;一方面,学校的事情;一方面,自己的脚本语言解释器;一方面,炒股。结果忙的焦头烂额。解释器这边写完了token,parser,在最后的运行器上卡住了,现在正在想办法攻克。然后学校的事情,现在已经告于段落。私活优先级相对较高,一直没落下。公司的事也都按部就班。炒股,最近因为牛市,也赚了不少。算法么,每天也都在刷。就是各方面的进度都不是特别好把握。还是觉得之前在学校,一段时间专注的做一件事情。这样的状态是最好的。 对目前的状况还是比较满意,一份不错的薪水,不忙的工作,自由的时间。每周还可以抽出三四天跑步,还是比较惬意的。看到身边的同事毕业三年买房买车还是比较羡慕的。不过,这也都是要靠自己的双手赚出来的。不过开心的是,手上的装备全都换了。自从上一家实习单位尝到了mac的痛快之后,我用了现在两个月的薪水加上之前的积蓄,将手里的所有设备都换成了Apple,成了正宗的苹果粉。不过,确实,这对我的编程效率的提升还是很有帮助的。平时的一些生活的安排,苹果确实帮了很多。各个设备上的同步,确实非常爽。 最近又用股票的盈利买了咖啡机,彻底脱离了速溶咖啡的坑。从磨咖啡都开始,慢慢的泡出一杯满意的咖啡,这感觉也是不错的。当然,这种只有在慵懒的周末的早晨才有机会,其余的都是晚上弄好,一起床开始泡。 开始渐渐的找到工作的感觉,也开始准备了今年的打算。年底圣诞想去一趟英国,以色列,还有西藏。顺便把车也学了。然后也想办法积累一点人脉,为自己之后做一个铺垫。对于读研,这个我准备到明年的时候看情况是不是准备。研究生是必须要读的,至于读什么方向,读什么类型,这个还是要再斟酌。 马上去跑步了。就这样。流水账般记录了一些事情,总之感觉一切都像写程序一样: Everything is under control.