【剑指offer-C++】JZ19： 正则表达式匹配

题目描述

描述：请实现一个函数用来匹配包括’.‘和’*‘的正则表达式。
1.模式中的字符’.‘表示任意一个字符。
2.模式中的字符’*'表示它前面的字符可以出现任意次（包含0次）。
在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配。

数据范围:
1.str 只包含从 a-z 的小写字母。
2.pattern 只包含从 a-z 的小写字母以及字符 . 和 *，无连续的 ‘*’。
3. 0≤str.length≤26 。
4. 0≤pattern.length≤26。

输入："aaa","a*a"
返回值：true
说明：中间的*可以出现任意次的a，所以可以出现1次a，能匹配上 

输入："aad","c*a*d"
返回值：true
说明：因为这里 c 为 0 个，a被重复一次， * 表示零个或多个a。因此可以匹配字符串 "aad"。

输入："a",".*"
返回值：true
说明：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）

输入："aaab","a*a*a*c"
返回值：false

解题思路

正则表达式匹配：最直观的想法是，递归，由于*比较特殊，其表示前面的字符重复0次、1次、多次，故需要分情况讨论。首先判断pattern是否为空，如果其为空，str也为空，那么可以匹配，反之如果str不为空，那么不可以匹配；接着我们使用first来表示pattern和str的第一位是否匹配，由于前面pattern为空时会返回，故到这里pattern肯定不为空，此时pattern和str第一位匹配的条件是str不为空，并且pattern[0]等于str[0]或者pattern[0]等于’.‘；然后我们根据’*‘来分情况讨论，由于’*‘不能单独使用，其前面至少要有一个字符，所以每次都是判断pattern[1]，如果pattern[1]等于’*‘，那么有两种情况，一是’*‘重复0次，那么就是比较str和以pattern[2]开头的字符串是否匹配，二是’*‘重复1次或者多次，两者都是以first为前提再比较以str[1]开头的字符串和pattern是否匹配，反之如果pattern[1]不等于’*'，那么以first为前提再比较以str[1]开头的字符串和pattern[1]是否匹配。

bool match(string str, string pattern) 
{//base1：p空 s空 匹配//base2：p空 s不空 不匹配if(pattern.empty()) return str.empty();//判断p和s的第一位是否匹配，其中走到这里说明p肯定不为空，故此处需要显示要求s也不为空bool first=(!str.empty())&&(str[0]==pattern[0]||pattern[0]=='.');//如果p的第二个为*，则分为重复0次和重复多次，重复0次即s和p[2]开始的字符串匹配与否，重复多次就是建立在p和s的第一位匹配上且s[1]和p开始的字符串匹配与否if(pattern.length()>=2&&pattern[1]=='*')return (first&&match(str.substr(1),pattern))||match(str,pattern.substr(2));//否则看p和s第一位匹配的基础上，s[1]和p[1]开始的字符串是否可以匹配上elsereturn first&&match(str.substr(1),pattern.substr(1));
}

优化：由于涉及到状态转移，那么可以用递归做的也可以用动态规划来做。其中dp[i][j]表示str的前i位与pattern的前j位是否匹配，其对应的是str[i-1]和pattern[j-1]，注意区分元素位置和元素下标。首先进行初始化，注意当str为空串的时候，pattern不为空串也是有可能匹配的，只需要通过*和*前面一位来两位两位的不断删除即可。在正式dp[i][j]赋值时，首先判断pattern当前元素是否为*，如果是则匹配0次或者1次或者多次，0次就是dp[i][j-2]，1次或者多次就是dp[i-1][j]，并且str的当前元素与pattern的当前元素的前一位匹配，相当于又重复了一次，反之如果不是则需要str的前i-1位与pattern的前j-1位匹配并且str的当前元素与pattern的当前元素匹配。最后返回dp[str.size()][pattern.size()]即可。

bool match(string str, string pattern) 
{int len1=str.size(),len2=pattern.size();vector<vector<bool>> dp(len1+1,vector<bool>(len2+1,false));  //dp[i][j]表示str的前i位与pattern的前j位是否匹配dp[0][0]=true; //两个空字符串肯定匹配for(int j=1;j<len2+1;j++) //初始化str为空而pattern不为空的情况，看是否可以使得pattern两位两位的不断删除从而变成空串与str匹配{//dp对应的下标表示的是从1开始的字符串位数而pattern和str对应的下标是从0开始的字符串元素下标//*不能作为第一个元素，其前面要有元素if(pattern[j-1]=='*'&&j-1>=1){dp[0][j]=dp[0][j-2];}}for(int i=1;i<len1+1;i++){for(int j=1;j<len2+1;j++){//如果pattern当前元素为*则需要分类讨论，dp[i][j-2]表示*匹配0次，后者dp[i-1][j]是表示str的前i-1位都和pattern的前j位匹配，且str当前元素与pattern当前元素的前一位匹配，其表示匹配1次或者多次if(pattern[j-1]=='*')dp[i][j]=dp[i][j-2]||(dp[i-1][j]&&(str[i-1]==pattern[j-2]||pattern[j-2]=='.'));//否则str的前i-1和pattern的前j-1位匹配并且两者的当前元素也匹配elsedp[i][j]=dp[i-1][j-1]&&(str[i-1]==pattern[j-1]||pattern[j-1]=='.');}}return dp[len1][len2];
}