博文中会简要介绍Leetcode P0010题目分析及解题思路。
“Regular Expression Matching”其实一道General的题目变换而来的，这道题的解题思路是动态规划，而这道题的原型其实是寻找最长公共子串。
Given an input string (s) and a pattern (p), implement regular expression matching with support for ‘.’ and ‘*’.
’.’ Matches any single character.
‘*’ Matches zero or more of the preceding element. The matching should cover the entire input string (not partial).Note:
s could be empty and contains only lowercase > letters a-z. p could be empty and contains only lowercase > letters a-z, and characters like . or *.
为什么这道题的原型是寻找最长公共子串？
如果我们将这道题进行划归，会发现如果母串s和模式串p是互相的公共子串，则p可以匹配s，而这道题只不过多了'*'和'.'这两个通配符而已，本质上就是判定s和p是否互为公共子串，所以实质上是寻找最长公共子串的一种衍生题。
既然将这题划归为寻找最长公共子串的衍生题，则理所当然的解法是动态规划。考虑如下数学递推式：
令dp[i][j]为动态规划最优解空间，i是s中第i个字符，同理可知j，
dp[0][0] = true;
显然两个空串之间互相匹配
dp[i][0] = false, i>0;
显然非空s中的子串不能匹配任何空串
dp[0][i] = dp[0][i-2], if p[i-1] == '*';
其余情况皆不匹配，当p[i-1]是'*'时，可以代表0个前缀字符，则此时关注空串是否和p[i-3]匹配
dp[i][j] = dp[i-1][j-1], if s[i-1] == p[j-1] or p[j-1] == '.';
若当前字符匹配或通配，则是否匹配取决于前缀序列是否匹配
dp[i][j] = dp[i][j-2] || ((s[i-1] == p[j-2] || p[j-2] == '.') && dp[i-1][j]), if p[j-1] == '*';
这个情况需要重点关注。若当前p是通配符'*'，则存在两种情况，一是认为该通配符匹配0个前缀字符，所以关注是否于p[j-3]匹配；或者是，该通配符匹配，则要求p[j-2]和s的字符相同或为通配符'.'，并且s[i-1]的前缀字符必须也匹配该通配符。
以上数学递推式中，重点在于最后一个递推式。而最后一个递推式中，第一个情况很好理解，关键在于第二个情况。
为什么s[i-1]的前缀字符必须也匹配该通配符？
其实很简单，如果s[i-1]的前缀字符，即s[i-2]，也匹配该通配符p[j-1]的话说明s[i-2]匹配p[j-3]或者s[i-2]匹配p[j-2]，前者是认为该通配符'*'匹配0个前缀字符所以相当于s[i-2]匹配p[j-3]，后者则是s[i-2]也属于该通配符的匹配范围，如此一来就能保证前缀序列是相互匹配的，而这也是当前递推式满足最优子结构的必要条件。
以下是Java的题解代码实现。
class Solution {
public boolean isMatch(String s, String p) {
if (s == null || p == null)
return false;
char[] sChars = s.toCharArray();
char[] pChars = p.toCharArray();
boolean[][] dp = new boolean [sChars.length+1][pChars.length+1];
dp[0][0] = true;
for (int idx=1; idx<=sChars.length; ++idx)
dp[idx][0] = false;
for (int idx=1; idx<=pChars.length; ++idx) {
if (pChars[idx-1] == '*')
dp[0][idx] = dp[0][idx-2];
}
for (int i1=1; i1<=sChars.length; ++i1) {
for (int j2=1; j2<=pChars.length; ++j2) {
if (sChars[i1-1] == pChars[j2-1] || pChars[j2-1] == '.') {
dp[i1][j2] = dp[i1-1][j2-1];
}
else if (pChars[j2-1] == '*') {
dp[i1][j2] = dp[i1][j2-2] || ((sChars[i1-1] == pChars[j2-2] || pChars[j2-2] == '.') && dp[i1-1][j2]);
}
else {
dp[i1][j2] = false;
}
}
}
return dp[sChars.length][pChars.length];
}
}
以下是C++的题解代码实现。
class Solution {
public:
bool isMatch(string s, string p) {
vector<vector<bool>> dp(s.length()+1, vector<bool>(p.length()+1, false));
dp[0][0] = true;
for (int idx=1; idx<=s.length(); ++idx)
dp[idx][0] = false;
for (int idx=1; idx<=p.length(); ++idx) {
if (p[idx-1] == '*')
dp[0][idx] = dp[0][idx-2];
}
// DP
for (int i1=1; i1<=s.length(); ++i1) {
for (int j2=1; j2<=p.length(); ++j2) {
if (p[j2-1] == s[i1-1] || p[j2-1] == '.') {
dp[i1][j2] = dp[i1-1][j2-1];
}
else if (p[j2-1] == '*') {
dp[i1][j2] = dp[i1][j2-2] || (dp[i1-1][j2] && (p[j2-2] == s[i1-1] || p[j2-2] == '.'));
}
else
dp[i1][j2] = false;
}
}
return dp[s.length()][p.length()];
}
};