每日一练（剑指offer）正则表达式匹配

描述

请实现一个函数用来匹配包括'.'和'*'的正则表达式。

1.模式中的字符'.'表示任意一个字符

2.模式中的字符'*'表示它前面的字符可以出现任意次（包含0次）。

在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配

数据范围:

1.str 只包含从 a-z 的小写字母。

2.pattern 只包含从 a-z 的小写字母以及字符 . 和 *，无连续的 '*'。

示例

输入：

"aaa","a*a"

返回值：

true

说明：

中间的*可以出现任意次的a，所以可以出现1次a，能匹配上

思路????????

/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param str string字符串
* @param pattern string字符串
* @return bool布尔型
*
* C语言声明定义全局变量请加上static，防止重复定义
*
* C语言声明定义全局变量请加上static，防止重复定义
*/
#include <stdbool.h>
bool match(char* str, char* pattern ) {
// write code here
int len1 = strlen(str);
int len2 = strlen(pattern);
int** dp = calloc(len1 + 1, sizeof(int*));
for (int i = 0; i <= len1; i++) {
dp[i] = calloc(len2 + 1, sizeof(int));
    }
dp[0][0] = 1;
//初始化第0行，即str为空，需要pattern的*全取0次
//第0列，即pattern为空，则只有dp[0][0]匹配，第一列其他位置肯定为0，不需要进行额外的初始化
for (int j = 2; j <= len2; j++) {
if (pattern[j - 1] == '*')
dp[0][j] = dp[0][j - 2];
    }
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (str[i - 1] == pattern[j - 1] || pattern[j - 1] == '.')
dp[i][j] = dp[i - 1][j - 1];
else if (j > 1 && pattern[j - 1] == '*') {
if (pattern[j - 2] == '.' || pattern[j - 2] == str[i - 1])
dp[i][j] = dp[i - 1][j] || dp[i][j - 2]; //j-1+1 || j-1-1
else
dp[i][j] = dp[i][j - 2]; //'*'取0次
            }
        }
    }
if (dp[len1][len2])
return true;
else
return false;
}