banxi1988
V2EX  ›  算法

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

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

虽然时间慢了点.代码比较多, 但是整个结构还是挺清晰的.
状态机笨解法尝试matching
10 条回复  •  2016-12-22 14:32:53 +08:00
Thoxvi
   1
Thoxvi  
   2016 年 12 月 21 日 via Android
请问楼主的状态机是在编译原理里学的还是离散数学里学的？还是单独一门课？( ´∵｀)
xcv58
   2
xcv58  
   2016 年 12 月 21 日 via iPhone
这道题目要求不是完整的正则实现，有很多取巧的方法
jedihy
   3
jedihy  
   2016 年 12 月 22 日   ❤️ 1
其实 v2 有算法节点了，是我提议开的，可以发在那个节点。

@xcv58 我用 DP 做的，算取巧吗？
lsmgeb89
   4
lsmgeb89  
   2016 年 12 月 22 日
@jedihy 终于有算法节点了，一个技术论坛居然到现在才有算法节点……
jedihy
   5
jedihy  
   2016 年 12 月 22 日
@lsmgeb89 /go/algorithm
太多莫名其妙的吐槽贴，月经贴还有就是设备讨论帖感觉拉低了 v2 的技术内涵，其实这里大牛很多的。
xcv58
   6
xcv58  
   2016 年 12 月 22 日
@jedihy 应该还不是最巧妙的，讨论区有更精简的写法。具体方法忘记了。

但说实话，对这种的题目不感兴趣。无聊且过于浪费时间，写出来的东西还基本上不可能用于实践中。
Rice
   7
Rice  
   2016 年 12 月 22 日 via iPhone
@Thoxvi 应该是计算理论课里的吧
banxi1988
   8
banxi1988  
OP
   2016 年 12 月 22 日
@Thoxvi 我是从 一本叫 "计算的本质" 的书上学的. 以前不知道学过没有, 估计有学但是没注意听.
Thoxvi
   9
Thoxvi  
   2016 年 12 月 22 日 via Android
@Rice 我记得学长有次发编译原理的笔记里就有…
Thoxvi
   10
Thoxvi  
   2016 年 12 月 22 日 via Android
@banxi1988 有次在图书馆里看到一本
形式语言与状态机
就对这个有了点印象所以想问问
关于  ·  Language
© 2026 V2EX · 29ms · 3.9.8.5