题目
题目链接
剑指offer：正则表达式匹配
题目描述
请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符.表示任意一个字符，而*表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配。
解题思路
1.分析题目
- 输入：一个待匹配字符串，一个待匹配正则表达式
- 输出：字符串与正则表示式相匹配则输出
true，否则输出false - 条件：正则表达式中仅含两个特殊字符;
.表示任意一个字符，*表示它前面的字符能够出现0~无数次。题目未说明是否贪心匹配(即尽可能多的匹配)的情况下，应默认非贪心匹配。即应考虑类似aaa与a*aa相匹配的情况。同时注意可能会出现.*这类能够匹配所有字符的表达式。
2.可能出现的情况
考虑字符串和正则相匹配时能够相消去，则当最终两者为空时为匹配成功；中途有不匹配且不带*的字符或是最终不能相互消去时为匹配失败。这种情况很显然使用指针移动特别好用。
考虑情况如下：
- 字符串空时，正则式不为空。后者剩余字符若皆为带/*字符，则应继续消去。
- 当前指针指向字符能够消去时(正则式当前指针字符与字符串当前指针字符相同，或是正则式当前指针字符为
.且字符当前指针不为\0)，需要考虑正则指针的下一步指向是否为*。为*则需要考虑此时是否非贪心匹配。 - 当前指针指向字符不可相互消去时，需考虑正则指针下一步指向是否为
*，为*则可忽略正则指针此时的不匹配字符，令其向前移两位；否则直接匹配失败。例如aaa与ab*c*aa能匹配成功。
3.思考解题步骤
在2中所考虑的情况都能够用起初的思路--指针移动解决，故确定以指针为解题方向。
同时，每一步对于当前指针指向字符的处理过程都是相似的，故考虑使用递归使代码更加简洁。
很惭愧，在编写2中指针字符相互消去的情况时，我发现自己写的代码总是会遗漏部分情况，查看错误样例后发现对*的非贪心匹配处理要写出大量逻辑繁琐且容易出错的代码。在查看讨论区的解答后，发现自己一直走了死胡同。对于这种问题应考虑使用动态规划的思想，将情况一分为二的处理，分别计算继续判断当前*与结束当前*匹配的情况。
具体代码
class Solution {
public:
bool match(char* str, char* pattern)
{
if (*str == '\0' && *pattern == '\0')
return true;
// 1.匹配带*正则(包括非贪心情况)
if (*str == *pattern || (*pattern == '.' && *str != '\0'))
{
// 不是正则式
if (*(pattern + 1) != '*')
return match(++str, ++pattern);
// 是正则式
// 将*字符的匹配一分为二的处理
return match(str, pattern + 2) || match(str + 1, pattern);
}
// 消去无用带*字符
else if (*(pattern + 1) == '*')
{
pattern += 2;
return match(str, pattern);
}
return false;
}
};