正则表达式匹配（递归+剑指offer）

发布时间：2020-12-14 00:57:04 所属栏目：百科来源：网络整理

导读：正则表达式匹配参与人数：660 时间限制：1秒空间限制：32768K 通过比例：14.97% 最佳记录：0 ms|8552K （来自高鹏）题目描述请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（

正则表达式匹配

参与人数：660时间限制：1秒空间限制：32768K
通过比例：14.97%
最佳记录：0 ms|8552K（来自高鹏）

题目描述

请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配

链接：http://www.nowcoder.com/practice/45327ae22b7b413ea21df13ee7d6429c?rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题意：点可以表示任意字符，星*表示前一个字符可以出现0--n次，那么用递归来解，条件是str串和pattern串到达结尾，或者str串结尾了，pattern串没有结尾，都退出。

而递归的条件是：遇到*，则三个出口，(str+1,pattern+2),(str+1,(str,pattern);

遇到'.' (str+1,pattern+1);

#include<cstdio>
using namespace std;
class Solution {
public:
    bool match(char* str,char* pattern)
    {
//        puts(str);
//        puts(pattern);
        if(str==NULL && pattern==NULL)
            return true;
        if(str==NULL || pattern==NULL)
            return false;
        return matchCore(str,pattern);
    }
    bool matchCore(char *str,char *pattern)
    {
        if(*str=='' && *pattern=='') {return true;}
        if(*str!='' && *pattern=='') return false;
        if(*(pattern+1)=='*')
        {
            if(*str==*pattern || (*pattern=='.'&&*str!=''))
            {
                //move on the next state
                return matchCore(str+1,pattern+2)
                //stay on the current state
                || matchCore(str+1,pattern)
                //ignore a '*'
                || matchCore(str,pattern+2);
            }
            else return matchCore(str,pattern+2);
        }
        if(*str==*pattern||(*pattern=='.'&&*str!=''))
        {
            return matchCore(str+1,pattern+1);
        }
        return false;
    }
};
int main()
{
    char ch1[]="";
    char ga1[]="";
    char *ch=ch1;
    char *ga=ga1;
    Solution so;
    if(so.match(ch,ga))printf("truen");
    else printf("falsen");
    return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!