最近在攻略动态规划,在做正则表达式匹配的时候看错了题目,发现写出来的是通配符匹配,后来看了下什么是正则表达式才明白过来。这两道题都是有很多解法的题目,按照标签刷题目还是限制了自己的思路,一开始就没有往其它地方想。事实上,通配符匹配用贪心算法(可以看做一种特殊的动态规划)更合适。

动态规划

什么是动态规划呢?简单的说就是一个问题有许多子问题,每个子问题只求解一次,这就是动态规划。更详细一点,就是根据当前的状态,推得以后时刻的状态。在动态规划问题中不必纠结使用什么样的方式,不论迭代还是回溯递归,只有使用一种策略,利用已有结果,就是动态规划。

动态规划的英文是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];
	}
};

 

发表评论

邮箱地址不会被公开。 必填项已用*标注