题思路及其代码

像这种两个字符串的问题一般都是定义二维的dp表按照两个字符串的第i和j下标位置来解决问题的。

所以在这里定义dp[i][j]表示p在区间[1,j]中的字符是否存在能够匹配s在[1i]中的字符。

2.状态转移方程

以s的第i个位置p的第j个位置为研究对象来研究问题。

此时分三种情况1.s[i]

p[j]或者p[j]

在以上i种情况下我们只要找到一个为真便可以了。

所以dp[i][j]

dp[i][j-1]||dp[i-1][j-1]||dp[i-2][j-1]||dp[i-3][j-1].....。

但是这样表示的话就需要遍历一遍所以我们必须要优化以上状态表达优化成为dp[i][j]

dp[i][j-1]||dp[i-1][j]。

通过数学推导得知将dp[i][j-1]后面的表达式转为一个状态表示。

3.s[i]!p[j]并且不是以上情况在这种条件下dp[i][j]直接就是false。

3.初始化

2.因为*是可以匹配空的所以当s字符串为空串时p为空串或者p全为*时也是可以匹配的。

初始化如下

根据状态转移方程很容易得出dp表的填写顺序是从左到右从上到下。

5.返回值

根据状态表示可知返回值是dp[m][n](m表示s的长度n表示p的长度)

class

p.size();vectorvectorbooldp(m1,vectorbool(n1));//dp[i][j]表示s,p分别以i,j结尾能不能完全匹配s

s;p

true;//初始化当我的s是一个空串时我的p都是*for(int

1;in1;i)

*){//这颗*可以若干个字符那可以配0个或者无数个得到的状态转移方程如下//如果不匹配dp[i][j]

dp[i-2][j-1]//.......//在上面的情况中我们只要找到一种便可以//dp[i][j]

dp[i][j-1]||dp[i-1][j-1]||dp[i-2][j-1]||dp[i-3][j-1]......//优化将上面的i个表达式变成n个表达式表示dp[i][j]

dp[i][j]

但是这道题跟第一道题何其相似啊.和?匹配规则是一样的但是注意两个题目的*的匹配规则是是不一样的。

所以在*和初始化处就要稍加改造了改造如下

初始化

dp[i][j-2]||dp[i-1][j];}else//不是.{//判断后再匹配if(p[j-1]

s[i]){dp[i][j]

dp[i][j-2]||dp[i-1][j];}else{dp[i][j]

dp[i][j-2];}}

p;//经典二维dp表vectorvectorbooldp(m1,vectorbool(n1));dp[0][0]

2;in1;i2)

p[j]){//i,j位置匹配上了就得看dp[i-1][j-1]dp[i][j]

dp[i-1][j-1];}else

dp[i][j-2]||dp[i-1][j];}else//不是.{//判断后再匹配if(p[j-1]

s[i]){dp[i][j]

dp[i][j-2]||dp[i-1][j];}else{dp[i][j]

dp[m][n];}

在看到三个字符串时我就已经犯蒙了。

感觉二维的dp表好像已经解决不了问题了但是其实是可以解决问题的。

解决步骤如下

1状态表示

仍然是开一个二维dp表dp[][]。

仍然以s1的第i个位置和s2的第j个位置为研究对象研究问题。

dp[i][j]表示s1的【1i]区间和s2的【1j】区间的字符能不能组成s3的【1ij】区间的字符。

2.状态转移方程

false;//二维数组表示以i,j位置为结尾能够组成s3的ijvectorvectorbooldp(m1,vectorbool(n1));//加上空格因为空格有意义s1

s1;s2

true;}else{break;}}//经典以i,j位置为研究对象for(int

1;im1;i){for(int