最近在攻略动态规划,在做正则表达式匹配的时候看错了题目,发现写出来的是通配符匹配,后来看了下什么是正则表达式才明白过来。这两道题都是有很多解法的题目,按照标签刷题目还是限制了自己的思路,一开始就没有往其它地方想。事实上,通配符匹配用贪心算法(可以看做一种特殊的动态规划)更合适。
动态规划
什么是动态规划呢?简单的说就是一个问题有许多子问题,每个子问题只求解一次,这就是动态规划。更详细一点,就是根据当前的状态,推得以后时刻的状态。在动态规划问题中不必纠结使用什么样的方式,不论迭代还是回溯递归,只有使用一种策略,利用已有结果,就是动态规划。
动态规划的英文是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]; } };