正则表达式匹配问题（'.'和'* '匹配） 题目描述： 给定一个字符串s和一个模式串p，实现支持'.'和'* '的正则表达式匹配。 '.'匹配任意单个字符 '* '匹配零个或多个前面的元素 匹配应该覆盖整个字符串s，而不是部分字符串。 解题过程： 问题分析： 这是一个经典的字符串匹配问题，需要处理两种特殊字符： '.'可以匹配任意单个字符 '* '可以匹配零个或多个前面的元素 状态定义： 定义dp[ i][ j ]表示字符串s的前i个字符与模式串p的前j个字符是否匹配。 初始化： dp[ 0][ 0 ] = true：两个空字符串匹配 对于第一行dp[ 0][ j]：处理模式串可能以"a* "、"b* "等形式开头的情况 对于第一列dp[ i][ 0 ] = false (i > 0)：非空字符串与空模式不匹配 状态转移方程： 情况1：当前字符匹配（包括'.'匹配） 如果s[ i-1] == p[ j-1] 或 p[ j-1 ] == '.'： dp[ i][ j] = dp[ i-1][ j-1 ] 情况2：遇到' ' 如果p[ j-1] == ' '： - 匹配0次：dp[ i][ j] = dp[ i][ j-2 ] - 匹配1次或多次：如果s[ i-1] == p[ j-2] 或 p[ j-2 ] == '.'： dp[ i][ j] = dp[ i-1][ j ] 详细推导示例： 以s = "aab"，p = "c a b"为例： 初始化： dp[ 0][ 0 ] = true 处理空字符串匹配：dp[ 0][ 1] = false, dp[ 0][ 2] = dp[ 0][ 0] = true (c* 匹配0次)... 逐步计算： dp[ 1][ 1]：'a' vs 'c'，不匹配，且下一个不是'* '，false dp[ 1][ 2]：'a' vs 'c* '，匹配0次，看dp[ 1][ 0 ]=false，false dp[ 1][ 3]：'a' vs '.'，匹配，看dp[ 0][ 2 ]=true，true dp[ 1][ 4]：'a' vs '.* '，匹配1次，看dp[ 0][ 4]=false 或 匹配0次看dp[ 1][ 2 ]=false，false dp[ 1][ 5 ]：'a' vs 'b'，不匹配，false 继续计算直到得到最终结果。 算法实现要点： 使用二维dp数组，大小为(len(s)+1) × (len(p)+1) 按行或按列遍历填充dp表 注意边界条件的处理 时间复杂度O(mn)，空间复杂度O(mn) 关键理解点： '* '的处理是最复杂的，需要考虑匹配0次、1次或多次的情况 当匹配多次时，实际上是通过dp[ i-1][ j ]来隐式处理的 初始化第一行很重要，处理模式串开头可能有多个"x* "的情况 这个问题的难点在于正确处理'* '的多种匹配情况，通过动态规划可以系统地处理所有可能性。