面试题19正则表达式匹配
题目:实现一个函数用来匹配包含‘.’和'*'的正则表达式,'.'可以代表任意字母,'*'表示他前面的字符可以出现>=0次,
#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 (*str == '\0'&&*pattern != '\0') { return false; } if (*str == *pattern || *pattern == '.') { if (*(pattern + 1) == '*') return matchCore(str+1, pattern) || matchCore(str+1, pattern + 2)||matchCore(str,pattern+2); else {
return matchCore(str + 1, pattern + 1);
}
}
/*else if (*pattern == '.')
{
if (*(pattern + 1) == '*')
return matchCore(str + 1, pattern) || matchCore(str, pattern + 2);
else
return matchCore(str + 1, pattern + 1);
}*/
else
{
if (*(pattern + 1) == '*')
{
return matchCore(str, pattern + 2);
}
else
return false;
}
}
bool match(char* str, char *pattern)
{
if (str == nullptr || pattern == nullptr)
return false;
return matchCore(str, pattern);
}
int main()
{
while (1){
char *str=new char[10];
char *pattern=new char[10];
cin.getline(str, 10);
cin.getline(pattern, 10);
cout << match(str, pattern) << endl;
delete[]str;
delete[] pattern;
}
return 0;
}
字符串匹配,两个穿str和pattern,第一个字母匹配时有三种情况,*str=*pattern,*pattern='.', *str!=*pattern
1.*str=*pattern
如果*(pattern+1)!='*';让后面的子串做匹配matchcore(str+1,pattern+1);(有点动态规划的意思?)
如果*(pattern+1)=='*' matchcore(str+1,pattern);
2.*pattern='.'
如果*(pattern+1)!='*';;让后面的子串做匹配matchcore(str+1,pattern+1)
如果*(pattern+1)=='*' matchcore(str,pattern+2)||matchcore(str+1,pattern+2)||matchcore(str+1,pattern) 分别代表情况,.*算0个字符或1个字符或2个字符,两个字符的情况很意思(这里调整一下或的顺序可以和第一种情况合并)
3.*str!=*pattern
如果*(pattern+1)=='*';;matchcore(str,pattern+2)
否则 return false;