思路
使用动态规划求解:
1.开辟一个二维数组 dp[i][j]来存放模式串的前j个元素与字符串的前i个元素是否匹配 初始化dp[0][0]为true(表示两个空串是匹配的)
2.如果第pattern[j]==str[i] 或者 pattern[j]=='.' 则 dp[i][j]=dp[i-1][j-1]
3.如果第j个元素是‘’,那么分两种情况有一种情况为true即可。
(1)第一种 a
出现0次,那么dp[i][j-2]==true即表示匹配成功
dp[i][j] = dp[i][j-2]
(2)第二种 a* 出现多次,那么就得是得第str[i]个元素与第pattern[j-1]个元素相等或者第pattern[j-1]个元素是‘.’ 并且dp[i-1][j]=true,则dp[i][j]为true