视频字幕
正则表达式匹配是一个经典的动态规划问题。给定一个字符串s和一个模式p，我们需要判断模式p是否能完全匹配字符串s。匹配规则包括：点号匹配任意单个字符，星号匹配零个或多个前面的字符。让我们通过一些基本示例来理解这些规则。
星号字符是正则表达式匹配中的核心难点。当我们遇到类似 a星 这样的模式时，它可以匹配零个、一个或多个a字符。这种灵活性使得我们需要考虑所有可能的匹配方式。例如，模式 a星b 可以匹配字符串b、ab、aab等。这种多样性正是问题复杂性的根源，也是我们需要使用动态规划来解决的原因。
动态规划是解决正则表达式匹配问题的关键思路。我们定义dp数组，其中dp[i][j]表示字符串s的前i个字符与模式p的前j个字符是否匹配。状态转移分为两种情况：当模式字符不是星号时，直接比较字符是否匹配；当模式字符是星号时，需要考虑匹配零次或多次的情况。通过这种递推关系，我们可以逐步构建出完整的解决方案。
今天我们来学习LeetCode第10题：正则表达式匹配。这是一个经典的动态规划问题。题目要求判断给定的字符串是否与包含特殊字符的模式完全匹配。模式中点号可以匹配任意单个字符，星号可以匹配零个或多个前面的字符。
解决这个问题的关键是使用动态规划。我们用dp数组记录子问题的解，其中dp[i][j]表示字符串前i个字符是否能与模式前j个字符匹配。对于非星号字符，直接比较是否匹配；对于星号，需要考虑匹配零次和多次两种情况。
现在让我们详细分析状态转移方程。首先是边界条件的处理，空字符串只能与空模式或特定星号模式匹配。对于非星号字符，只需检查当前字符是否匹配且前面的子问题为真。对于星号字符，需要考虑两种情况：匹配零次前面字符，或者匹配一次或多次。
现在让我们看具体的代码实现。首先初始化一个二维DP数组，然后处理边界条件，特别是空字符串与包含星号的模式的匹配情况。接下来是核心的双重循环，逐步填充DP表格。对于非星号字符，直接比较是否匹配；对于星号字符，需要考虑匹配零次和多次两种情况。最终返回DP数组右下角的值。
最后我们总结一下这个问题。时间复杂度是O(m乘以n)，空间复杂度也是O(m乘以n)。解题的关键是正确理解星号的含义，仔细处理边界条件，以及掌握动态规划的状态转移逻辑。这是一个非常经典的问题，通过这个例子，我们可以更好地理解动态规划在字符串匹配中的应用。
让我们通过一个完整的示例来演练整个算法过程。对于字符串aab和模式c星a星b，我们首先初始化DP数组，然后设置边界条件。在填充过程中，c星可以匹配零次被跳过，a星匹配字符串中的两个a，最后b匹配字符串中的b。通过逐步填充DP表格，我们最终在右下角得到True，表示匹配成功。这个完整的过程展示了动态规划如何系统地解决正则表达式匹配问题。