题目描述

请实现一个函数用来匹配包括’.’和’*’的正则表达式。

模式中的字符’.’表示任意一个字符，而’*’表示它前面的字符可以出现任意次（含0次）。

在本题中，匹配是指字符串的所有字符匹配整个模式。

例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但是与”aa.a”和”ab*a”均不匹配。

数据范围

输入字符串长度 [0,300]。

样例

输入：

s="aa"
p="a*"

输出:true

DFS

思路

1. 将*p转换成一个pattern数组，每个pattern记录它的字符，以及它是否使用了量词’*‘
2. 依次将s与pattern数据进行比对，当pattern当前元素使用了量词’*‘时，依次考虑量词为0~p与当前pattern元素匹配的最大个数时后面的正则匹配情况

C 代码

struct pattern_info
{
    char ch;
    int type;// 0: common ch; 1: *
};

bool search(char* s, struct pattern_info arr[], int pos, int count)
{
    int i = 0;
    bool result = true;

    if( pos >= count )
    {
        if( *s == '\0' )
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    else if( arr[pos].type == 1 )
    {
        if( *s == '\0' )
        {
            // 当s已遍历到结尾时，如果pattern为*，则需要后面所有元素都为*才可，因此搜索pattern下一个元素
            return search( s, arr, pos+1, count);
        }

        if( arr[pos].ch != '.' && *s != arr[pos].ch )
        {
            // 当s当前字符与当前pattern不匹配时，将量词*作为0次处理
            return search( s, arr, pos+1, count );
        }

        // '*' 处理
        result = true;
        for(i = 0; *(s+i) != '\0' ;i++ )
        {
            if( *(s+i) == *s || arr[pos].ch == '.' )
            {
                //连续字符相同
                if( pos+1 >= count )
                {
                    continue;
                }
                result = search(s+i, arr, pos+1, count);
                if( result == true )
                {
                    break;
                }
            }
            else
            {
                result = search(s+i, arr, pos+1, count);
                break;
            }
        }
        return result;
    }
    else
    {
        if( *s == '\0' || ( arr[pos].ch != '.' && arr[pos].ch != *s ) )
        {
            //s遍历结束 或 字符不匹配时，结束
            return false;
        }
        else
        {
            return search(s+1, arr, pos+1, count);
        }
    }
}

bool isMatch(char* s, char* p) {
    struct pattern_info pattern_info_arr[300];
    int arr_count = 0;
    char ch = *p;
    int i = 0;
    while( ( ch = p[i] ) != '\0' )
    {
        pattern_info_arr[arr_count].ch = ch;
        pattern_info_arr[arr_count].type = 0;


        if( p[i+1] == '*' ){
            pattern_info_arr[arr_count].type = 1;
            i++;
        }

        arr_count++;

        if( p[i+1] == '\0' ){
            break;
        }

        i++;
    }

    return search(s, pattern_info_arr, 0, arr_count);
}