首页 注册 登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
banxi1988
V2EX  ›  算法

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

  •   
  •   banxi1988 · 2016-12-21 22:40:53 +08:00 · 4158 次点击
    这是一个创建于 2894 天前的主题，其中的信息可能已经有所发展或是发生改变。
    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 23:31:02 +08:00 via Android
    请问楼主的状态机是在编译原理里学的还是离散数学里学的？还是单独一门课？( ´∵｀)
    xcv58
        2
    xcv58  
       2016-12-21 23:54:19 +08:00 via iPhone
    这道题目要求不是完整的正则实现，有很多取巧的方法
    jedihy
        3
    jedihy  
       2016-12-22 00:44:26 +08:00   ❤️ 1
    其实 v2 有算法节点了，是我提议开的，可以发在那个节点。

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

    但说实话，对这种的题目不感兴趣。无聊且过于浪费时间，写出来的东西还基本上不可能用于实践中。
    Rice
        7
    Rice  
       2016-12-22 07:47:07 +08:00 via iPhone
    @Thoxvi 应该是计算理论课里的吧
    banxi1988
        8
    banxi1988  
    OP
       2016-12-22 07:58:18 +08:00
    @Thoxvi 我是从 一本叫 "计算的本质" 的书上学的. 以前不知道学过没有, 估计有学但是没注意听.
    Thoxvi
        9
    Thoxvi  
       2016-12-22 14:31:38 +08:00 via Android
    @Rice 我记得学长有次发编译原理的笔记里就有…
    Thoxvi
        10
    Thoxvi  
       2016-12-22 14:32:53 +08:00 via Android
    @banxi1988 有次在图书馆里看到一本
    形式语言与状态机
    就对这个有了点印象所以想问问
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2922 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 14:21 · PVG 22:21 · LAX 06:21 · JFK 09:21
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.