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

动态规划

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

动态规划的英文是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但是不推荐。

通配符匹配

题目

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%,于是看了别人的代码,恍然大悟,这道题就贪心算法啊。

所以,数据结构类的可以按标签来耍,算法类的题目还是要自己想办法,毕竟一题多解,也是考察思维嘛。

贪心算法的解释写在代码注释里了,很简单的。

代码

 

发表评论

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