泪流满面. 我终于把这道 LeetCode 题搞通过了.

[banxi1988]

P10 : Regular Expression Matching 级别 Hard
去年有一天,看到题目比较好理解, 正好当时对正则比较有兴趣.就尝试了几次. 但是几次尝试都失败了. 原因是使用的是笨解法. 解决的方法不完备.
后来学了状态机,尝试使用状态机的方法来解决. 如下:
https://discuss.leetcode.com/topic/72534/share-my-swift-3-based-nfa-solution
主要使用了 NFA 加自由移动来解决.

虽然时间慢了点.代码比较多, 但是整个结构还是挺清晰的.

[Thoxvi]

请问楼主的状态机是在编译原理里学的还是离散数学里学的？还是单独一门课？( ´∵｀)

[xcv58]

这道题目要求不是完整的正则实现，有很多取巧的方法

[jedihy]

其实 v2 有算法节点了，是我提议开的，可以发在那个节点。

@xcv58 我用 DP 做的，算取巧吗？

[lsmgeb89]

@jedihy 终于有算法节点了，一个技术论坛居然到现在才有算法节点……

[jedihy]

@lsmgeb89 /go/algorithm
太多莫名其妙的吐槽贴，月经贴还有就是设备讨论帖感觉拉低了 v2 的技术内涵，其实这里大牛很多的。

[xcv58]

@jedihy 应该还不是最巧妙的，讨论区有更精简的写法。具体方法忘记了。

但说实话，对这种的题目不感兴趣。无聊且过于浪费时间，写出来的东西还基本上不可能用于实践中。

[Rice]

@Thoxvi 应该是计算理论课里的吧

[banxi1988]

@Thoxvi 我是从 一本叫 "计算的本质" 的书上学的. 以前不知道学过没有, 估计有学但是没注意听.

[Thoxvi]

@Rice 我记得学长有次发编译原理的笔记里就有…

[Thoxvi]

@banxi1988 有次在图书馆里看到一本
形式语言与状态机
就对这个有了点印象所以想问问