Home Sign Up Sign In
banxi1988
V2EX  ›  算法

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

  •   
  •   banxi1988 · Dec 21, 2016 · 5054 views
    This topic created in 3611 days ago, the information mentioned may be changed or developed.
    P10 : Regular Expression Matching 级别 Hard
    去年有一天,看到题目比较好理解, 正好当时对正则比较有兴趣.就尝试了几次. 但是几次尝试都失败了. 原因是使用的是笨解法. 解决的方法不完备.
    后来学了状态机,尝试使用状态机的方法来解决. 如下:
    https://discuss.leetcode.com/topic/72534/share-my-swift-3-based-nfa-solution
    主要使用了 NFA 加自由移动来解决.

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

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

    但说实话，对这种的题目不感兴趣。无聊且过于浪费时间，写出来的东西还基本上不可能用于实践中。
    Rice
    Rice
    Dec 22, 2016 via iPhone
    7
    @Thoxvi 应该是计算理论课里的吧
    banxi1988
    banxi1988
    OP
    Dec 22, 2016
    8
    @Thoxvi 我是从 一本叫 "计算的本质" 的书上学的. 以前不知道学过没有, 估计有学但是没注意听.
    Thoxvi
    Thoxvi
    Dec 22, 2016 via Android
    9
    @Rice 我记得学长有次发编译原理的笔记里就有…
    Thoxvi
    Thoxvi
    Dec 22, 2016 via Android
    10
    @banxi1988 有次在图书馆里看到一本
    形式语言与状态机
    就对这个有了点印象所以想问问
    About   ·   Help   ·   Advertise   ·   Blog   ·   API   ·   FAQ   ·   Privacy   ·   Solana   ·   966 Online   Highest 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 31ms · UTC 19:32 · PVG 03:32 · LAX 11:32 · JFK 14:32
    ♥ Do have faith in what you're doing.