LeetCode Problem 10 Regular Expression Matching

背景

我会的编程就是会几个 if else for 的程度。

算法确实大学里面是有课程，但是我大学都逃课来着。所以顶天就是知道快速排序这几个字怎么写。

目标就是通过此次学习提高一下自己的能力。

也许 LeetCode 会需要过几遍。 第一遍的目标就用我自己的想法来解决问题。

想要学一个新语言，就用 LeetCode 来边学边做了。 本来看上 elixir 无奈 LeetCode 不支持。 Rust 思考了一下还是算了。 那就学 Golang 把。

以后除了解题思路以外还有我是如何用 Google 从零基础到成功提交的过程。

源码仓库

题目

英文版本

中文版本

本文具有强烈的个人感情色彩,如有观看不适,请尽快关闭. 本文仅作为个人学习记录使用,也欢迎在许可协议范围内转载或使用,请尊重版权并且保留原文链接,谢谢您的理解合作. 如果您觉得本站对您能有帮助,您可以使用RSS方式订阅本站,这样您将能在第一时间获取本站信息.

解题思路

看完题目以后一脸懵逼，就是需要实现一个特别简单的正则匹配。但是毫无头绪。所以 Google key “自己实现正则” 我把第一页的结果全部看一遍。

找到一句关键的话”正则表达式描述字符的集合。”

发现以下关键词

DFA
NFA
SML

继续 Google 这些 Key

DFA

NFA

SML

看完以后依然一脸懵逼。面对一堆计算机科学理论感觉自己就是个文盲。然后在某些文章里面看到「代码之美」里面有实现。随即找来看一眼。

然后理解了一下，我把这题从实现一个正则引擎，降解为，使用每个字母逐一对比的方法，查找一个字符串(input)中是否包”含另”外一个”字符串”(pattern)。

用「代码之美」里面实现的逻辑，写了一个 Golang 版本，其中发现 Golang 没有 do while 循环。用只能用 for 循环写。但是第一次提交不过。 仔细看题目。是需要全字符匹配。就一直修补，结果写了整整两天的代码还是没法提交过。有一些沮丧。

就直接看了眼 Discuss 里面的回复

发现关键词 DP

又一脸懵逼，继续 Google 动态规划

找到一篇挺好的文章,仔细研读一番。

顺藤摸瓜的找到这份电子书整理自公众号 labuladong

然后逐一看动态规划系列文章直到发现动态规划之正则表达

看了以后，改进之前「代码之美」里面的递归实现。把他的 Python 翻译为 Golang。 11行就搞定了。 汗颜，递归耍的还是不够溜啊。

Golang 参考

Package strings

Go 语言设计与实现 3.3 字符串

Strings, bytes, runes and characters in Go

2 patterns for a do-while loop in Go

总结

递归不够溜，数学逻辑思维已经退化到小学三年级水平。需要再接再厉啊。

硬广时间

我目前现生活在新西兰。

如果是新晋奶爸可以看看婴儿奶粉

如果逢年过节孝敬父母可以逛逛澳新保健品

如果经常熬夜或喝酒，你需要程序员神器-护肝片

大量澳新产品均可通过么么爪海购精选购买。

么么爪海购精选上的价格在海外直邮模式上有一定优势，但是跟国内电商上大量低价商品没法比。优势上只能用我自己那可能并不存在的人品担保都是正品。