xfeif / leetcode Goto Github PK
View Code? Open in Web Editor NEW🌵Clean and beautiful leetcode solutions! Just do it!
License: MIT License
🌵Clean and beautiful leetcode solutions! Just do it!
License: MIT License
判断字符串匹配。给定输入string
s, 和一个pattern
p,判断p是否能匹配整个s。
这里有两个需要注意的字符:
.
可以匹配任意单个字符;*
可以表示它前面的字符重复0次或者多次。.*
可以表示任意长度的串。True
: .
匹配任意单个字符,匹配且只匹配一个。False
:acby
多了y
, cb
中a
不匹配。True
: *
表示a
重复0次或多次。False
: b
至少出现一次,a*
不能表示ac
。True
: a*
表示a
重复0次或多次,.*
表示b
,y
之间可以有任意字符串False
: 缺少b
或y
首先我们确定一下这是哪种题型。
我们通过上面的样例进一步分析,一般我们设两个指针,分别用来标记字符串和pattern的位置,对应位置字符相同,我们就比较下一个,出现特殊字符的时候,需要进一步考虑。直到最后比完。
我们知道,如果s[i+1]
和p[j+1]
能够匹配上,那么从开头到i+1
是否能够完全匹配上,取决于s[0...i]
和p[0...j]
匹配的结果,并且当前比较是不受前面比较的影响。于是我们可以将两个完整串的匹配分解成一个个独立的子问题来解。
再想想动态规划的两个性质(最优子结构,重叠子问题),不难想到这题属于动态规划(DP)问题。那么我们就针对DP问题的解法来思考。
在判断出本题属于DP问题后,我们需要以下三步走:
根据上面的分析,我们可以使用s[0...i]
和p[0...j]
的匹配状态作为整体的状态,那么我们需要一个二维的状态矩阵dp
,纬度分别为len(s)+1
,len(p)+1
。
首先初始化dp
,若s
,p
均为空串则dp[0][0]=True
,若二者只有一个为空串,那么均匹配失败。
if s[i] == p[j]
or p[j] == '.'
, dp[i][j] = dp[i-1][j-1]
;
elif p[j] == '*'
,这个时候要分两种情况考虑。一是*
前的字母出现0次,那么当前状态应取决于,当前字符位和匹配串前两位之前的匹配状态,即dp[i][j] = dp[i][j-2]
。另一种情况,考虑前面的字符出现了一次或多次,即将s[i]
与p[j-1]
比较,或者匹配串前一个字符p[j-1]
为.
,这种情况下,dp[i][j] = dp[i-1][j]
,综合考虑起来,就是取二者的或
。
留给自己二刷补充。
总结:直觉的数学思路(化简) + 一些 python 语言细节。
1WA,2TLE 以及参考了其他人的做法才解出来。
首先简单的地方在于最简单的基本情况只有一个字符,很好判断。
复杂的地方在于表达式嵌套,想找到一种方法解嵌套。
自己举几个例子可以发现,每一个基本情况都需要计算。也就是与或非三个基本表达式,那么问题转化为将每个基本情况都计算出来,然后进行化简。
再深入一层,需要找到每个基本情况。
我最开始尝试采用递归的方法,肯定可以做出来。但是我没有,我在处理一些特殊情况的时候,考虑不全面以及写的很复杂,相当于是每种特殊情况我都要列出来……
打开讨论界面,标题里出现次数比较多的关键词是stack。
考虑一下,用栈的方式的话,读取表达式,每次都可以先处理一个基本情况,将基本情况转化为t或者f,这样一直把复杂表达式中子表达式化简成最简形式,最后得到的表达式也就是最简形式了。
What Today
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.