[力扣_10] 正则表达式匹配

题目入口:点击进入

相关算法:

  • 动态规划——时间复杂度O(sleng*pleng),空间复杂度O(sleng*pleng)

思路和算法:

对于这道题来说,多看视频和多看代码就可以清楚的了解,我们通过案例来看:

img

红框框住的部分,表示状态转移方程的初始部分,匹配串p作用于二维数组的列,主串s作用于二维数组的行,我们不断枚举主串s的每一个子串去对匹配串p做匹配,来递推出主串与匹配串是否匹配,dpi表示主串s的前i和字符是否能被匹配串的前j个字符匹配

这道题给了两个通配符:“.”和“*”,作用如下:

  • .:它可以匹配任意非空字符
  • *:他作用于他的前一个字符,他可以让前一个字符出现一次或者多次,又或者出现零次

从上我们可以发现,可以分解为下列子问题:

  • 若匹配串的当前字符为‘.’,则它可以匹配任意字符,除了空字符外(初始条件在两串头端添加了空字符),它的状态都是true
  • 若匹配串的当前字符和主串的当前字符相等,则是true
  • 若匹配串的当前字符为‘*’

(难点来了)

  • 当前字符的上一个字符不出现,则就等于匹配串排除当前字符和上一个字符的状态,若前两个字符与主串匹配,则是true,因为*可以视为前一个字符不出现
  • 当前字符的上一个字符出现一次或多次,

    第一种情况为false后,代表上一个字符不出现的情况是不匹配的

    ,这个时候就要看上一个字符与主串当前的字符是否匹配

    • 如果匹配,或者前一个字符为'.'(.可以匹配任何字符),则就可以直接copy匹配串上一个字符的状态(*号前一个字符出现多次)
    • 如果不匹配,则它出现多少次也不能匹配,因为号只能copy号的前一个字符,则当前字符的状态就直接是false

从上分析下来这道题就不难懂了,因为存在输入空串的情况(字符串最短长度就为0),所以在两串头端添加空串可以把所有情况都考虑到。

配合以下视频观看:

题目与动态规划教程

这题我就老老实实琢磨dp了,题解里边的大佬,真捉摸不透,呜呜呜

测试代码如下所示:

#define TRUE 1
#define FALSE 0
#include<stdio.h>
#include<stdlib.h>

typedef struct
{
    char* ch;
    int length;
}String;

int REM(String S, String T);
void StrAssign(String* S, char* a)
{
    int i;
    for (i = 0; a[i]; i++);

    S->ch = (char*)malloc(sizeof(char) * i + 1);
    S->length = 0;
    for (int j = 1; j <= i; j++)
    {
        S->ch[j] = a[j - 1];
        S->length++;
    }
}

int main()
{
    String S, T;
    StrAssign(&S, //输入测试用例);
    StrAssign(&T, //输入测试用例);
    if (REM(S, T))
    {
        printf("TRUE");
    }
    else
    {
        printf("FALSE");
    }
    system("pause");
    return 0;
}

int REM(String S, String T)
{   
    /*初始化状态变量*/
    int** dp;
    dp = (int**)malloc(sizeof(int*) * S.length + 1);
    for (int i = 0; i <= S.length; i++)
    {
        *(dp + i) = (int*)malloc(sizeof(int) * T.length + 1);
    }

    dp[0][0] = TRUE;

    for (int i = 1; i <= S.length; i++)
    {
        dp[i][0] = FALSE;
    }




    /*正式进入状态转移方程*/
    int i, j;
    for (i = 0; i <= S.length; i++)
    {
        for (j = 1; j <= T.length; j++)
        {
            if (S.ch[i] == T.ch[j] || T.ch[j] == '.' && i >= 1)
            {
                dp[i][j] = dp[i - 1][j - 1];
            }
            else if(T.ch[j] == '*')
            {
                if (dp[i][j - 2] == TRUE)
                {
                    dp[i][j] = TRUE;
                }
                else
                {
                    if (S.ch[i] == T.ch[j - 1] || T.ch[j - 1] == '.')
                    {
                        dp[i][j] = dp[i - 1][j];
                    }
                    else
                    {
                        dp[i][j] = FALSE;
                    }
                }
            }
            else
            {
                dp[i][j] = FALSE;
            }
        }
    }



    /*输出状态转移方程*/
    for (int m = 0; m <= S.length; m++)
    {
        for (int n = 0; n <= T.length; n++)
        {
            printf("%d", dp[m][n]);
        }
        printf("\n");
    }


    return dp[i - 1][j - 1];
}

LeetCode代码:

bool isMatch(char * s, char * p){
    int sleng=strlen(s);
    int pleng=strlen(p);
    int dp[sleng+1][pleng+1];
   dp[0][0]=true;
   //状态转移方程的初始条件
   for(int i=1;i<=sleng;i++)
   {
       dp[i][0]=false;
   }
   for(int j=1;j<=pleng;j++)
   {
       if(p[j-1]=='*')
       {
           dp[0][j]=dp[0][j-2];
       }
       else
       {
           dp[0][j]=false;
       }
   }
   //正式状态转移方程
   for(int i=1,m=0;i<=sleng;i++,m++)
   {
       for(int j=1,n=0;j<=pleng;j++,n++)
       {
           if(s[m]==p[n]||p[n]=='.')
           //第一种情况:当两字符匹配或匹配串为通配符'.'的时候
           //当前状态就等于上一次匹配的状态
           {
               dp[i][j]=dp[i-1][j-1];
           }
           else
           {
               if(p[n]=='*')
               //当匹配符为'*'的时候,分两种情况:
               //1.前一个字符出现0次,则就等于他前两个字符的状态
               //2.前一个字符出现1次或多次,则判断他前一个字符是否与主串当前字符相等
               //如若相等,则他就等于他前一个字符的匹配状态。
               {
                   if(dp[i][j-2]==true)//出现0次的情况
                   {
                       dp[i][j]=true;
                   }
                   else
                   {
                       if(s[m]==p[n-1]||p[n-1]=='.')//出现一次或多次的情况
                       {
                           dp[i][j]=dp[i-1][j];
                       }
                       else
                       {
                           dp[i][j]=false;//若前一个字符不想等,则直接为false
                       }
                   }
               }
               else
               {
                   dp[i][j]=false;//如若不为.也不为*,两字符也不相等,则直接为false
               }
           }
       }
   }
   return dp[sleng][pleng];//返回它的最终状态
}

状态转移方程如下:

    /*初始化矩阵状态转移方程初始条件*/
    dp[0][0] = true;
    //拿空串与两串做匹配,分配为0行的所有列与0列的所有行的状态

    for (int i = 1; i <= sleng; i++)
    {
        dp[i][0] = false;//主串的所有字符与空字符匹配必定不相等
    }
    for (int j = 1; j <= pleng; j++)//模式串中除了*号,其余字符与空字符必定不相等
    {
        if (j >= 2 && p[j] == '*')
        {
            dp[0][j] = dp[0][j - 2];
        }
        else
        {
            dp[0][j] = false;
        }
    }


    /*二维矩阵做状态变量*/
    for (int i = 1; i <= sleng; i++)//主串做行
    {
        for (int j = 1; j <= pleng; j++)//匹配串做列
        {
            /*第一种情况*/
            if (s[i] == p[j] || p[j] == '.')//主串当前的字符与模式串当前字符匹配,或模式串字符为'.'则可匹配
            {
                dp[i][j] = dp[i - 1][j - 1];
            }
            /*第二种情况*/
            else if (j >= 2 && p[j] == '*')//模式串当前字符为'*',且*前面要跟一个字符
            {
                if (dp[i][j - 2] == true)//*前面字符出现0次的情况
                {
                    dp[i][j] = true;
                }
                else//*前面的字符出现多次的情况
                {
                    if (s[i] == p[j - 1] || p[j - 1] == '.')//判断主串当前字符与*前一个字符是否相等(如果相等则可以复制前一个字符)
                    {
                        dp[i][j] = di[i - 1][j];
                    }
                    else
                    {
                        dp[i][j] = false;
                    }
                }
            }
            else
            {
                dp[i][j] = false;
            }
        }

本文链接:

https://nullcode.fun/56.html
1 + 1 =
快来做第一个评论的人吧~