各位看官别怪我少见多怪，连这么经典的题目都要拿出来说一遍。但是对于字符串和DP同时相关的题目我是真不熟练。。。这不么，我争取从0到1讲一讲Leetcode 第10题怎么做。
先上题
就是字符串匹配，多俩条件
一是"." "." 匹配任意单个字符
二是“*” “*” 匹配星号之前的一个字符的0次到多次的重复出现。看好了斜体字，要有大学问呢。
好了 接下来就是匹配吧 怎么匹配呢？
首先我们确定一点，这个排序是连续排序 而且是从各自的起点开始的。这个没有问题吧？
好没有问题，什么意思呢，我们最优的可能一定是这样的
假设 s从0 到i p从0到j 对吧，我们就一个一个比较i和j的位置就可以了。
如果两个符号都没有，好说， s[i] == p[j]就是条件。
如果算上. 的话，p[j] == '.' 就不用看s[i]是什么了，肯定匹配。
好了 难点来了 "*" 怎么办。
我们之前说什么来着？
“*” 匹配星号之前的一个字符的0次到多次的重复出现。
什么意思？
一般来说两种情况咯？0次出现和1次以上出现。
为什么这么判断？
因为关键题目说了是一个字符的多次出现，如果是两个或者以上字符这道题目就麻烦了。
因为是一个字符的多次出现，所以我们可以有如下式子
假设p[j-1] == ‘*’ 判断match[i][j]的条件是
s[i] match p[j-2] 就是新出来的这个字符匹配星号前面的字符。
s[i-1] matchp[j] 就是在s到i之前，已经形成匹配了。
注意哦 这个是很重要的一个点 因为一般来说 一个到多个匹配很难想 怎么样能够用一个式子表达这个关系，反正我自己之前做的时候是觉得很难得。
所以 这道题目的递推关系也就出来了
然后代码如下
欢迎大家指正 如果哪里我写的不清楚还请评论 我争取多阐述一下
网友评论