最近在攻略动态规划，在做正则表达式匹配的时候看错了题目，发现写出来的是通配符匹配，后来看了下什么是正则表达式才明白过来。这两道题都是有很多解法的题目，按照标签刷题目还是限制了自己的思路，一开始就没有往其它地方想。事实上，通配符匹配用贪心算法（可以看做一种特殊的动态规划）更合适。
动态规划
什么是动态规划呢？简单的说就是一个问题有许多子问题，每个子问题只求解一次，这就是动态规划。更详细一点，就是根据当前的状态，推得以后时刻的状态。在动态规划问题中不必纠结使用什么样的方式，不论迭代还是回溯递归，只有使用一种策略，利用已有结果，就是动态规划。
动态规划的英文是Dynamic Programming，其中的Programming意思是表格，在动态规划中最重要就是表格了，根据表格中已有问题的解，得到后续问题的解，这就需要建立状态转移方程。
动态规划问题看似复杂（事实上确实很复杂），但是解决问题的套路是非常一致的，两个要点：表格+状态转移方程。根据状态转移方程又分为一阶和二阶，二阶就是状态转移方程又两个，一个全局，一个局部，这个在LeetCode中也常常遇到（比如股票买卖问题）。基本套路在算法导论中都已经提到了。
在算法导论中介绍了三道典型的题目，一道是钢条切割的题目（使用备忘表），第二道是矩阵链乘法（使用划分链），第三道是公共子序列。我们发现这两道题题目和公共子序列是同一种类型。在建立动态规划时，两个数组是规划表的两个维度，然后根据已有内容推得后续内容。
正则表达式匹配
如果还不知道正则表达式是什么，可以看菜鸟教程。
题目
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). The function prototype should be: bool isMatch(const char *s, const char *p) Some examples:
- isMatch(“aa”,”a”) → false
- isMatch(“aa”,”aa”) → true
- isMatch(“aaa”,”aa”) → false
- isMatch(“aa”, “a*”) → true
- isMatch(“aa”, “.*”) → true
- isMatch(“ab”, “.*”) → true
- isMatch(“aab”, “c*a*b”) → true
Subscribe to see which companies asked this question.
分析
这道题可以用回溯（Back Tracking）解，但是时间开销会比较大，于是动态规划就是一个不错的解了。
| a | b | c | d | |
| a | √ | |||
| * | ||||
| b | √ | |||
| * | ||||
| b | √ | |||
| * | ||||
| c | × | |||
| d | × |
我们建立的就是上面这样的表格，在这里我们必须要对正则表达式有基本的认识才能正确的分析问题。a*b* 这个表达式中，a*要一起来看，所以我们总是要检查后面第二个字符是否有*。如果后面第二个字符不是*，那么只匹配当前字符，就可以了。
1. 如果s[i] 匹配 p[j]，且p[j+2]!=’*’，那么s[i+1] == p[j+1]，那么s[i+1] p[j+1]就是匹配的，否则不匹配
2. 那么如果是p[j+2] == * ，问题来了，这时如果s[i+1] == p[j+1]，就会导致两种匹配成立
2.1 s[i]与p[j+2]匹配
2.2 s[i+1]与p[j]匹配
这样我们就可以建立状态转移方程了，只不过是一个各种与或关系的方程，直接看代码里的方程吧。
另外一点就是边界条件，这里的表格在最前面多加了一行一列，用来表示空串，这样方便书写DP的边界条件。
代码
代码中还包含了一种回溯的方法，虽然也AC但是不推荐。
class Solution {
public:
bool isMatch(string s, string p){
int slen = s.size(), plen = p.size();
vector<vector<bool>> dp(slen+1, vector<bool>(plen+1));
dp[0][0] = true;
for (int i = 1; i <= slen; ++i){
dp[i][0] = false;
}
for (int j = 1; j <= plen; ++j){
dp[0][j] = j > 1 && p[j - 1] == '*' && dp[0][j - 2];
}
for (int i = 1; i <= slen; ++i){
for (int j = 1; j <= plen; ++j){
if (p[j - 1] == '*'){
dp[i][j] = dp[i][j-2] ||
(s[i-1] == p[j-2] || '.' == p[j-2]) && dp[i-1][j];
} else{
dp[i][j] = dp[i-1][j-1] && (s[i-1] == p[j-2] || '.' == p[j-2]);
}
}
}
return dp[slen][plen];
}
bool isMatchMy(string s, string p) { // BackTrack
if (p.empty()){
return s.empty();
}
if (p.size() == 1){
if (s.size() != 1){
return false;
}
if (s[0] == p[0] || '.' == p[0]){
return true;
} else{
return false;
}
}
if (p[1] == '*'){
if (s.empty()){
return isMatch(s, p.substr(2));
}
if (s[0] == p[0] || '.' == p[0]){
return (isMatch(s.substr(1), p) || isMatch(s, p.substr(2)));
} else{
return isMatch(s, p.substr(2));
}
} else{
if (s.empty()){
return false;
}
if ((s[0] == p[0]) || ('.' == p[0])){
return isMatch(s.substr(1), p.substr(1));
} else{
return false;
}
}
return false;
}
};
通配符匹配
题目
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). The function prototype should be: bool isMatch(const char *s, const char *p) Some examples:
- isMatch(“aa”,”a”) → false
- isMatch(“aa”,”aa”) → true
- isMatch(“aaa”,”aa”) → false
- isMatch(“aa”, “a*”) → true
- isMatch(“aa”, “.*”) → true
- isMatch(“ab”, “.*”) → true
- isMatch(“aab”, “c*a*b”) → true
分析
通配符匹配问题也可以套用上面动态规划的思路，建立一个二维表格
分析状态变化：当没有*的时候直接匹配，遇到*的时候，如果之前的字符串是匹配的，那么这个新加入的*会导致两种匹配，一是如果s[i-1]与p[j]匹配 或者 s[i-1]与p[j-1] 或者 s[i]与p[j-1]匹配，那么s[i]与p[j]匹配，这个很好理解，ba 与 b*匹配，会有b与b*匹配和baa与b*匹配，二是s[i+1]与p[i+1]匹配。
博主自己就是按照上面的方法写了，边界条件调试了好久，虽然AC，但是一看只超过10%，于是看了别人的代码，恍然大悟，这道题就贪心算法啊。
所以，数据结构类的可以按标签来耍，算法类的题目还是要自己想办法，毕竟一题多解，也是考察思维嘛。
贪心算法的解释写在代码注释里了，很简单的。
代码
class Solution {
public:
bool isMatch(string s, string p){
int slen = s.size(), plen = p.size();
int i = 0, j = 0, is = -1, ip = -1;
while (i < slen) {
if (p[j] == '*'){ // {is, ip}为遇到*通配符的位置
is = i;
ip = j++;
} else{
if (s[i] == p[j] || p[j] == '?'){
i++;
j++;
} else if(ip == -1){
return false;
} else { // 如果之前出现过通配符，并且当前不在通配符位置，切当前字符不匹配，那么从上个通配符多通配一个位置，从该位置重新开始查找
i = ++is; // 通配符多通配一个位置
j = ip + 1; // 从通配符之后可是匹配
}
}
}
while (j < plen && p[j] == '*'){
j++;
}
return j == plen;
}
bool isMatchMyDP(string s, string p) {
const int n1 = s.size();
const int n2 = p.size();
if (!n1 || !n2){
if (!n1 && !n2){
return true;
}
if (n2 == 0){
return false;
}
for (int j = 0; j < n2; ++j){
if (p[j] != '*'){
return false;
}
}
return true;
}
vector<vector<bool>> m(n1, vector<bool>(n2));
m[0][0] = ((s[0] == p[0]) || (p[0] == '?') || (p[0] == '*'));
for (int i = 1; i < n1; ++i){
m[i][0] = (p[0] == '*');
}
bool flag = ((p[0] == '?') || (p[0] == s[0]));
for (int j = 1; j < n2; ++j){
if (flag){
m[0][j] = ((p[j] == '*') && m[0][j - 1]);
}
else{
m[0][j] = (((p[j] == '*') || (p[j] == '?') || (p[j] == s[0])) && m[0][j - 1]);
if (p[j] == '?' || p[j] == s[0]){
flag = true;
}
}
}
for (int i = 1; i < n1; ++i){
for (int j = 1; j < n2; ++j){
m[i][j] = (m[i - 1][j - 1] && ((s[i] == p[j]) || p[j] == '?'))
|| ((p[j] == '*') && (m[i - 1][j - 1] || m[i][j - 1] || m[i - 1][j]));
}
}
return m[n1 - 1][n2 - 1];
}
};