《劍指offer》:[53]正則表達式匹配
來源：程序員人生 發布時間：2016-06-30 13:15:52 閱讀次數：2424次
題目：請實現1個函數用來匹配包括’.’和’‘的正則表達式。模式中的字符’.’表示任意1個字符，而’‘表示它前面的字符可以出現任意次（包括0次）。在本題中，匹配是指字符串的所有字符匹配全部模式。例如，字符串”aaa”與模式”a.a”和”ab*ac*a”匹配，但是與”aa.a”和”ab*a”均不匹配。
分析；常規中，如果是普通的兩個字符串，那很簡單，我們直接進行對照就能夠了，這里又是要求匹配是指字符串的所有字符匹配全部模式，所以只要直接挨個比較就能夠了，如果都相等則返回true；否則返回false；可是這個題目來了1個'.'和'*'兩個比較煩人的東西，它改變了游戲的規則。把游戲變的復雜多變。
首先要明確'.'肯定了字符的個數為1，并且為任意；'*'可以肯定它前面的字符的個數包括0次；
第1種情況：當模式的第2個字符不是'*'的時候，如果字符串的第1個字符和模式串的第1個字符相等，則都向后移動1個，匹配剩下的字符串和模式串。如果不等則直接返回false；
第2種情況：當模式的第2個字符是'*'的時候，這時候候就稍復雜點兒，由于這時候候存在不同的幾種匹配方式：以字符串"aaa"與模式"ab*ac*a"匹配為例：
1、如果模式串中的字符和字符串中的字符不等如(a)，且模式串的第2個字符為'*'。
選擇只有1種：在模式串上向后移動兩個字符,疏忽掉b和*，由于'*'可以匹配0個字符；以下圖：
2、如果模式串中的字符和字符串中的字符相等如(b)，或模式串中為'.'如(c)，并且模式串的第2個字符為'*'。其實(b)和(c)是1樣的。這時候候選擇有3種情況：
（1）可以選擇在模式串上向后移動兩個字符,疏忽掉b和*，由于'*'可以匹配0個字符，字符串str保持不變；
（2）可以選擇超出'*'，'*'前的a當作有效的字符，且數量為1，str++；
（3）可以選擇模式串pattern不變，由于‘*’前的a可以任意數量的，并且和字符串str相等，只需要str++便可；
具體以下圖所示：
具體實現代碼以下：
#include <iostream>
using namespace std;
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'))//將‘*’號疏忽，‘*’前的作為1個有效的值；
return MatchCore(str+1,pattern+2)
|| MatchCore(str+1,pattern) //‘*’號前可以出現任意個，所以pattern可以保持不變
|| MatchCore(str,pattern+2);//疏忽‘*’及‘*’號之前的字符；
else
return MatchCore(str,pattern+2);//由于‘*’ 號前的字符與*str不等，所以只能疏忽*pattern字符1個選擇；
}
if(*str==*pattern || (*pattern=='.' && *str!='\0'))
return MatchCore(str+1,pattern+1);//正常的字符串比較；
return false;
}
bool match(char *str,char *pattern)
{
if(str==NULL || pattern==NULL)
return false;
return MatchCore(str,pattern);
}
int main()
{
char str[]="aaa";
char *pattern[4]={"a.a","ab*ac*a","aa.a","ab*a"};
for(int i=0;i<4;i++)
{
if(match(str,pattern[i]))
cout<<"The same!"<<endl;
else
cout<<"Not the same!"<<endl;
}
system("pause");
return 0;
}
運行結果：
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
