题目链接

题目描述

给定一个文本串和一个匹配串,问匹配串是否可以构成文本串,如果可以构成就输出"yes",否则就输出"no"。
文本串和匹配串都由大小写构成,但是匹配串当中包含了特殊的字符:'.'可以代替任意一种的字符,'*'可以将上一个字符前面与他相同的删除,也可以无限将前面的字符向后拓展,也可以不做任何操作。

解题思路

DP思想,开一个二维的dp数组,存放匹配串和文本串分别为i,j时 是否满足匹配。如果满足,值为真,否则值为假,最后判断dp[len2][len1]是否为真即可。
DP的思想

  • 当文本串和匹配串相同,或者匹配串为.则满足为真的条件但要注意这里的dp应该是dp[i][j] = dp[i - 1][j - 1];只有前面都满足这才能为真。
  • 当匹配串的字符为 * ,当匹配串为*的时候,可以进行向前删除也可以向后填充字符,满足其中一个那么dp[i][j] = true;
  • 特殊情况第二个为可以起到删除前面的字符的作用,所以dp[i][0] = true;

代码部分