剑指offer(C++)-JZ19：正则表达式匹配(算法-动态规划)-创新互联
作者：翟天保Steven
版权声明：著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处
请实现一个函数用来匹配包括'.'和'*'的正则表达式。
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，能匹配上解题思路：
本题考察算法-动态规划算法的使用。具体思路如下：
1.建立动态规划表，s1行，s2列，表示进行到某个位置时的匹配状态，默认均为false。
2.初始化首位置为true。首列除了（0,0）位置全为false，首行有可能因为*字符而出现true的情况，所以要处理下。
3.先考虑不为*的情况，这类情况比较简单。当出现.符号或者字符相同时，当前位置匹配成功；若上一层判断是true，则表示整体匹配成功；若上一层为false，即使当前匹配成功，整体也是失败的。
4.再考虑有*符号的情况，这个要继续细分。A：*前的字符是.或者能与str对应位置字符一致。B：不一致。
5.A类情况，此时有两种可能使得匹配成功。
一是x*这两个字符等于空，字符x的数量当做0处理，只参考去除这两个字符后是否匹配成功，如下图所示。如果dp[i][j-2]是true，则true，是false则false。
二是将x字符重复匹配，其实上面的情况可以看做是0个b，若str中出现了连续的b，则连续匹配，匹配的依据就是dp[i-1][j]的状态，直到连续字符中断。如下图所示。
综合来看，A类场景的匹配依据就可以归纳为：dp[i-1][j]和dp[i][j-2]有一个是true，dp[i][j]就可以匹配成功。
6.A类场景搞懂了，B类自然不难理解。因为字符不一致了，所以只能把x*这两个字符当做空，再结合dp[i][j-2]的匹配状态来判断是否匹配成功。
7.以上就是完整思路，可以自己画个表，便于理解。
测试代码：class Solution {
public:
// 匹配
bool match(string str, string pattern) {
int s1 = str.length();
int s2 = pattern.length();
// 建立动态规划表
// dp[i][j]表示str前i个字符是否与pattern前j个字符匹配
vector>dp(s1 + 1, vector(s2 + 1, false));
// 双空串可匹配
dp[0][0] = true;
// 处理当str为空时的情况
for(int j = 2; j<= s2; ++j)
{
if(pattern[j - 1] == '*')
{
dp[0][j] = dp[0][j - 2];
}
}
// 双层循环
for(int i = 1; i<= s1; ++i)
{
for(int j = 1; j<= s2; ++j)
{
// 考虑不为*的情况
// 当出现.符号或者字符相同时，当前位置匹配成功
// 若上一层判断是true，则表示整体匹配成功；若上一层为false，即使当前匹配成功，整体也是失败的
if(pattern[j - 1] != '*' && (pattern[j - 1] == '.' || pattern[j - 1] == str[i - 1]))
{
dp[i][j] = dp[i - 1][j - 1];
}
// 若出现*符号，则继续分情况考虑
else if(j >= 2 && pattern[j - 1] == '*')
{
// 若*前的字符是.或者能与str字符串的第i-1个字符一致，则进入该分支
if(pattern[j - 2] == '.' || pattern[j - 2] == str[i - 1])
{
// 如果dp[i][j-2]是true，并赋给dp[i][j]，意味着x*这两个字符等于空，把字符x的数量当做0处理，此时匹配成功
// 如果dp[i][j-2]是false，说明前面的匹配链是断开的
// 但有一个机会能完成匹配，那就是*前面的字符和str中对应位置字符一致
// 但还需要dp[i-1][j]是true才行，它是true的条件其实就等同于字符x连续重复了多次
// 综上，dp[i-1][j]和dp[i][j-2]有一个是true，dp[i][j]就可以匹配成功
dp[i][j] = dp[i - 1][j] || dp[i][j - 2];
}
else
{
// 如果进入该分支，那说明*前的字符和str字符串的第i-1个字符不一致
// 不一致却能匹配成功的情况，就只能是x*这两个字符为空，也就是把字符x的数量当0处理
// 而dp[i][j-2]又是true才可以
dp[i][j] = dp[i][j - 2];
}
}
}
}
return dp[s1][s2];
}
}; 你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
网页题目：剑指offer(C++)-JZ19：正则表达式匹配(算法-动态规划)-创新互联
本文网址：http://6mz.cn/article/djgeio.html