题目
请实现一个函数用来匹配包含
.和*的正则表达式。模式中的字符.表示任意一个字符，而*表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。
例如，字符串aaa与模式a.a和ab*ac*a匹配，但与aa.a和ab*a均不匹配。
-
aaa与a.a相匹配，那是因为.表示任意一个字符，即当.为a时，两个字符串自然相等，匹配传给。 -
aaa与ab*ac*a匹配，那是因为*表示它前面的字符可以出现任意次（含0次），即当字符串ab*ac*a中*前面的字符出现0次时，ab*ac*a正好为aaa -
aa.a和ab*a很显然是不匹配的
思路
总的思路：每次从字符串里拿出一个字符和模式中的字符去匹配
1、当模式中的第二个字符不是*时
- 如果字符串第一个字符和模式中的第一个字符相匹配，那么字符串和模式都后移一个字符，然后匹配剩余的。
- 如果字符串第一个字符和模式中的第一个字符相不匹配，直接返回
false。
2、当模式中的第二个字符是*时
如果字符串第一个字符跟模式第一个字符不匹配，则模式后移2个字符，继续匹配。
如果字符串第一个字符跟模式第一个字符匹配，可以有2种匹配方式：
- 字符串后移1字符，模式后移2字符(相当于*被忽略)；
- 字符串后移1字符，模式不变，即继续匹配字符下一位，因为*可以匹配多位；
具体例子分析
如何匹配一个字符：如果模式中的字符
ch是'.'，那么它可以匹配字符串中的任意字符。如果模式中的字符ch不是'.'，而且字符串中的字符也是ch，那么它们相互匹配。当字符串中的字符和模式中的字符相匹配时，接着匹配后面的字符
当模式中的第二个字符不是*时，问题要简单很多。如果字符串中的第一个字符和模式中的第一个字符相匹配，那么在字符串和模式上都后移一个字符，然后匹配剩余的字符串和模式。如果字符串中的第一个字符和模式中的第一个字符不相匹配，则直接返回false
当模式中的第二个字符是*时，问题要复杂一些，因为可能有多种不同的匹配方式。一种选择是在模式上向后移动两个字符。这相当于*和它前面的字符被忽略了，因为*可以匹配字符串的0个字符。
如果模式中的第一个字符和字符串中的第一个字符相匹配，则在字符串上后移一个字符，而在模式上有两种选择：可以在模式上向后移动两个字符，也可以保持模式不变
如下图，当匹配进入状态2并且字符串的字符是'a'时，我们有两种选择：可以进入状态3（在模式上向后移动两个字符），也可以回到状态2（模式保持不变）
download.jpg
算法实现
bool matchCore(char *str, char *pattern);
bool match(char *str, char *pattern)
{
// 任意字符串为空，匹配失败
if (str == nullptr || pattern == nullptr)
return false;
return matchCore(str, pattern);
}
bool matchCore(char *str, char *pattern)
{
// 任意字符串结束，匹配成功
if (*str == '\0' && *pattern == '\0')
return true;
// 字符串未结束，而模式匹配结束，那么匹配失败
if (*str != '\0' && *pattern == '\0')
return false;
// 判断模式的当前字符的下一个字符是否是*
if (*(pattern + 1) == '*')
{
// 当前字符匹配成功
if (*pattern == *str || (*pattern == '.' && *str != '\0'))
return matchCore(str + 1, pattern + 2) || // 移动下一个状态
matchCore(str + 1, pattern) || // 保持当前状态
matchCore(str, pattern + 2); // 忽略*
else
return matchCore(str, pattern + 2); // 忽略*
}
// 如果当前字符的下一个字符不是*，并且字符相等，或者当字符串未结束的情况下，模式字符为.，那么当前字符匹配成功，进行下一个字符匹配
if (*str == *pattern || (*pattern == '.' && *str != '\0'))
return matchCore(str + 1, pattern + 1);
return false;
}
参考
《剑指offer》
网友评论