题目地址：

https://www.lintcode.com/problem/regular-expression-matching/description

给定一个字符串$s$和一个模式串$p$，$p$中含字母，'.'或者'*'。其中'.'可以匹配任何单个字符，'*'可以匹配其之前的字符重复$0$次或大于等于$1$次。问$s$是否符合$p$所代表的模式。

该题的思考方式与Wildcard Matching这个问题非常相似，可以参考https://blog.csdn.net/qq_46105170/article/details/109214129。下面详细说明。

思路是动态规划。设$f[i][j]$是$s$的前$i$个字符是否能匹配模式串$p$里的前$j$个字符（$i$和$j$都是从$1$开始计数）。我们可以按照$p[j-1]$是如何与$s$匹配的来分类： 1、若$p[j-1]$是字母或者是'.'，那么$p[j-1]$要必然与$s[i-1]$进行匹配，并且要求$p[0:j-2]$与$s[0:i-2]$要匹配。此时$$f[i][j]=(p[j-1]=.\vee p[j-1]=s[i-1])\wedge f[i-1][j-1]$$2、若$p[j-1]$是'*'，那么这个'*'连同其前一个字符应该看成一个整体： 如果这个整体按照出现$0$次来匹配，那么结果就是$f[i][j-2]$（此时需要保证$j\ge 2$，事实上如果$p$是个合法的模式串，应该有如果$p[j-1]$是'*'那么$j\ge 2$。但如果$p$不合法，我们也应该返回false。所以这里还是需要额外判断一下$j\ge 2$，只是为了将不合法的情形包含进去）； 如果这个整体按照出现大于等于$1$次来匹配，那么就要求或者$p[j-2]$是'.'，或者$s[i-1]=p[j-2]$，这个整体匹配完之后，还需要$s[0:i-2]$与$p[0:j-1]$匹配，也就是还要求$f[i-1][j]$为true。注意，这里是$p[0:j-1]$，因为那个整体是匹配大于等于$1$次的出现，将$s$末字符匹配完之后，前面有可能还有$s[i-1]$出现，也就是那个整体匹配的一部分是$s[i-1]$而不是全部。 综上，此时：$$f[i][j]=f[i][j-2]\vee ((p[j-2]=.\vee p[j-2]=s[i-1])\wedge f[i-1][j])$$考虑初始条件，空字符串可以和空模式匹配，而非空字符串无法和空模式匹配，所以$f[0][0]$是true，而当$i>0$时，$f[i][0]$是false。但是$f[0][j]$一下子是看不出来的，需要在递推的过程中算出来。代码如下：

public class Solution { /** * @param s: A string * @param p: A string includes "." and "*" * @return: A boolean */ public boolean isMatch(String s, String p) { // write your code here boolean[][] dp = new boolean[s.length() + 1][p.length() + 1]; for (int i = 0; i <= s.length(); i++) { for (int j = 0; j <= p.length(); j++) { // 对于j = 0的情况可以直接判断出来 if (i == 0 && j == 0) { dp[i][j] = true; } else if (j == 0) { dp[i][j] = false; } else { // 对于模式串非空的情形开始考虑。根据其最后一个字符是否是'*'来考虑 if (p.charAt(j - 1) != '*') { // 如果不是'*'，并且s非空，就先看该字符是否能匹配，然后看前面是否能匹配 if (i - 1 >= 0 && (p.charAt(j - 1) == s.charAt(i - 1) || p.charAt(j - 1) == '.')) { dp[i][j] = dp[i - 1][j - 1]; } } else { // 如果是'*'，并且p合法，那么先枚举x*整体是重复0次的情况 if (j - 2 >= 0) { dp[i][j] |= dp[i][j - 2]; } // 如果是'*'，并且p合法，并且s非空，那么s的最后一个字符应该匹配，匹配完之后s之前的字符也要和p匹配 if (i >= 1 && j >= 2) { dp[i][j] |= dp[i - 1][j] && (p.charAt(j - 2) == s.charAt(i - 1) || p.charAt(j - 2) == '.'); } } } } } return dp[s.length()][p.length()]; } }

时空复杂度$O(l_s{l}_p)$。