以下是C语言实现正则表达式的代码：

#include <stdbool.h>
#include <string.h>
#include <stdlib.h>

bool isMatch(char* s, char* p) {
    int m = strlen(s);
    int n = strlen(p);
    
    // 检查模式p的合法性，避免无效的'*'
    for (int i = 0; i < n; ++i) {
        if (p[i] == '*' && (i == 0 || p[i-1] == '*')) {
            return false;
        }
    }
    
    // 创建动态规划表，dp[i][j]表示s的前i个字符和p的前j个字符是否匹配
    bool *dp = (bool *)calloc((m+1) * (n+1), sizeof(bool));
    if (!dp) {
        return false; // 内存分配失败，但题目通常保证不会出现
    }
    
    // 初始化基础情况：空字符串匹配空模式
    dp[0] = true;
    
    // 初始化第一行，处理模式p可以匹配空字符串的情况（如"a*"）
    for (int j = 1; j <= n; ++j) {
        if (p[j-1] == '*') {
            dp[j] = dp[j-2]; // 匹配0次的情况
        }
    }
    
    // 填充dp表
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (p[j-1] == '*') {
                // 处理'*'的情况，考虑匹配0次或多次
                bool matchZero = dp[i*(n+1) + (j-2)];
                bool matchMore = (p[j-2] == '.' || s[i-1] == p[j-2]) && dp[(i-1)*(n+1) + j];
                dp[i*(n+1)+j] = matchZero || matchMore;
            } else {
                // 处理普通字符或'.'的情况
                bool currentMatch = (p[j-1] == '.' || s[i-1] == p[j-1]);
                dp[i*(n+1)+j] = currentMatch && dp[(i-1)*(n+1) + (j-1)];
            }
        }
    }
    
    bool result = dp[m*(n+1) + n];
    free(dp);
    return result;
}


void test(const char *s, const char *p, bool expected) {
    bool result = isMatch((char*)s, (char*)p);
    printf("s=\"%s\", p=\"%s\" -> %s (Expected %s)\n", 
           s, p, 
           result ? "true" : "false", 
           expected ? "true" : "false");
}

int main() {
    // 完全匹配
    test("aa", "aa", true);
    
    // '.' 匹配任意字符
    test("ab", "a.", true);
    
    // '*' 匹配零次
    test("a", "ab*", true);        // b* 匹配零次
    
    // '*' 匹配多次
    test("aaa", "a*", true);       // a* 匹配三次
    test("ab", "a*b", true);       // a* 匹配一次
    
    // 复杂组合
    test("aab", "c*a*b", true);    // c* 匹配零次，a* 匹配两次
    test("mississippi", "mis*is*p*.", false); // 无法匹配
    
    // 无效模式
    test("a", "a**", false);       // 连续 '*' 非法
    
    // 空字符串
    test("", "", true);            // 空字符串匹配空模式
    test("", "a*", true);          // a* 匹配零次
    
    // 边界情况
    test("a", ".*", true);         // .* 匹配任意字符
    
    return 0;
}

代码解析

1. 合法性检查
   确保模式 p 中的 * 不连续且不位于开头。例如 a** 或 *a 是非法的。
2. 动态规划表初始化

• 使用 calloc 分配 (m+1)*(n+1) 的布尔数组，初始值为 false。
• dp[i][j] 表示 s 的前 i 个字符与 p 的前 j 个字符是否匹配。

3. 基础情况

• dp[0][0] = true：空字符串与空模式匹配。
• 第一行处理模式 p 匹配空字符串的情况（例如 a* 可以匹配空）。

4. 填充表格

当 p[j-1] 是 * 时：

• matchZero：匹配零次（跳过 p[j-2]），即 dp[i][j-2]。
• matchMore：匹配多次（需 p[j-2] 与 s[i-1] 匹配），即 dp[i-1][j]。

5. 普通字符或 .：直接检查当前字符是否匹配，并依赖 dp[i-1][j-1]。
6. 结果提取与内存释放
   最终结果存储在 dp[m][n] 中，释放动态规划表内存。

算法复杂度

• 时间复杂度：O(m*n)，需填充 m*n 的表格。
• 空间复杂度：O(m*n)，使用一维数组模拟二维表。