題目
請實現(xiàn)一個函數(shù)用來匹配包含
.和*的正則表達式蔬捷。模式中的字符.表示任意一個字符，而*表示它前面的字符可以出現(xiàn)任意次（含0次）京髓。在本題中饰迹，匹配是指字符串的所有字符匹配整個模式。
例如醉锅，字符串aaa與模式a.a和ab*ac*a匹配兔簇，但與aa.a和ab*a均不匹配。
-
aaa與a.a相匹配硬耍，那是因為.表示任意一個字符垄琐，即當.為a時，兩個字符串自然相等经柴，匹配傳給狸窘。 -
aaa與ab*ac*a匹配，那是因為*表示它前面的字符可以出現(xiàn)任意次（含0次）口锭，即當字符串ab*ac*a中*前面的字符出現(xiàn)0次時朦前，ab*ac*a正好為aaa -
aa.a和ab*a很顯然是不匹配的
思路
總的思路：每次從字符串里拿出一個字符和模式中的字符去匹配
1、當模式中的第二個字符不是*時
- 如果字符串第一個字符和模式中的第一個字符相匹配鹃操，那么字符串和模式都后移一個字符，然后匹配剩余的春哨。
- 如果字符串第一個字符和模式中的第一個字符相不匹配荆隘，直接返回
false。
2赴背、當模式中的第二個字符是*時
如果字符串第一個字符跟模式第一個字符不匹配椰拒，則模式后移2個字符晶渠，繼續(xù)匹配。
如果字符串第一個字符跟模式第一個字符匹配燃观，可以有2種匹配方式：
- 字符串后移1字符褒脯，模式后移2字符(相當于*被忽略)；
- 字符串后移1字符缆毁，模式不變番川，即繼續(xù)匹配字符下一位，因為*可以匹配多位脊框；
具體例子分析
如何匹配一個字符：如果模式中的字符
ch是'.'颁督，那么它可以匹配字符串中的任意字符。如果模式中的字符ch不是'.'浇雹，而且字符串中的字符也是ch沉御，那么它們相互匹配。當字符串中的字符和模式中的字符相匹配時昭灵，接著匹配后面的字符
當模式中的第二個字符不是*時吠裆，問題要簡單很多。如果字符串中的第一個字符和模式中的第一個字符相匹配烂完，那么在字符串和模式上都后移一個字符硫痰，然后匹配剩余的字符串和模式。如果字符串中的第一個字符和模式中的第一個字符不相匹配窜护，則直接返回false
當模式中的第二個字符是*時效斑，問題要復(fù)雜一些，因為可能有多種不同的匹配方式柱徙。一種選擇是在模式上向后移動兩個字符缓屠。這相當于*和它前面的字符被忽略了，因為*可以匹配字符串的0個字符护侮。
如果模式中的第一個字符和字符串中的第一個字符相匹配敌完，則在字符串上后移一個字符，而在模式上有兩種選擇：可以在模式上向后移動兩個字符羊初，也可以保持模式不變
如下圖滨溉，當匹配進入狀態(tài)2并且字符串的字符是'a'時，我們有兩種選擇：可以進入狀態(tài)3（在模式上向后移動兩個字符）长赞，也可以回到狀態(tài)2（模式保持不變）
算法實現(xiàn)
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)
{
// 任意字符串結(jié)束，匹配成功
if (*str == '\0' && *pattern == '\0')
return true;
// 字符串未結(jié)束得哆，而模式匹配結(jié)束脯颜，那么匹配失敗
if (*str != '\0' && *pattern == '\0')
return false;
// 判斷模式的當前字符的下一個字符是否是*
if (*(pattern + 1) == '*')
{
// 當前字符匹配成功
if (*pattern == *str || (*pattern == '.' && *str != '\0'))
return matchCore(str + 1, pattern + 2) || // 移動下一個狀態(tài)
matchCore(str + 1, pattern) || // 保持當前狀態(tài)
matchCore(str, pattern + 2); // 忽略*
else
return matchCore(str, pattern + 2); // 忽略*
}
// 如果當前字符的下一個字符不是*，并且字符相等贩据，或者當字符串未結(jié)束的情況下栋操，模式字符為.闸餐，那么當前字符匹配成功，進行下一個字符匹配
if (*str == *pattern || (*pattern == '.' && *str != '\0'))
return matchCore(str + 1, pattern + 1);
return false;
}
參考
《劍指offer》
