更多

LeetCode-10 正则表达式匹配题解

这道题用状态机最直观,奈何功力还是不够,而且觉得解这题用状态机很麻烦,最后只好看题解用DP,DP对我来说真的难。。。

DP就是打表,但是这个表中每个元素代表啥意思比较难想,必须要多积累经验才行。本题表元素dp[i,j]表示s串前i个字符是否能够和模式串p前j个字符匹配,假设s串长度sl,p串长度pl,dp表大小应该为(sl+1)×(pl+1),于是dp[sl,pl]就是最终的解。状态转移方程如下:

这里主要是需要讨论p[j]的不同情况,如果p[j]不是星号,那就看p[j]与s[i]是否匹配,匹配的含义是指s[i]==p[j]或p[j]==’.’,若匹配那就看前边的是否匹配,若不匹配则dp[i,j]就是false。

若p[j]是星号,就得看s[i]和p[j-1]是否匹配,即s[i]是否和星号前那个字符匹配。若不匹配,那就得舍弃掉p[j-1]和p[j]这一对(任意字符加*表示匹配此字符0次或多次,这里不匹配,就表示匹配了0次,所以要舍弃掉这一对,去看舍弃这一对后的模式串是否能和s串匹配),看剩下的p是否能和s匹配,即dp[i,j]=dp[i,j-2]。若匹配,就要往前看,看把s[i]扔掉,剩下的s[0..(i-1)]是否还能匹配上p,或者看把p[j-1]和p[j]这一对舍弃后,剩下的p[0..(j-2)]是否能和s匹配上(即a*a*这种情况,本质上是尝试尽可能多地消除模式串,最大化匹配)

这里有个问题,就是边界dp[0,j]和dp[i,0]表示什么?显然i=0或j=0时表示s串或p串为空串,dp[0,0]就表示s和p都是空串,这时肯定是匹配的,即dp[0,0]=true,于是初始状态就有了。那么当j为0时表示模式串为空,如果s串不为空,那就肯定匹配不上,因此dp[i,0]=false,i≠0。而当i为0时,表示s串为空,这时就要讨论模式串p的情况了。

考虑p=”a*b*c*”这种情况,表示的是0或多个a加0或多个b加0或多个c,也就是说如果s串为空串时,仍然能够匹配上,因此不能简单地认为s串为空时p串永远匹配不上,也就是说不能简单认为dp[0,j]=false,j≠0。仔细观察p串,发现p[j]=’*’时,只要p[j-2]为true,则p[j]就为true,这是因为p[j-1]在p[j](也就是’*’号)作用下,可以将其消除,只要看p[j-2]是不是true就好了,其背后的含义是p去掉数字加星后的前j-2号能不能匹配得上s的前i号。

C#
string s = "abaab";
string p = "c*a*ba.*b";

Solution solution = new();
Console.WriteLine(solution.IsMatch(s, p));

public class Solution
{
    public bool IsMatch(string s, string p)
    {
        int sl = s.Length;
        int pl = p.Length;
        s = '+' + s;
        p = '+' + p;

        bool[,] dp = new bool[sl + 1, pl + 1];
        dp[0, 0] = true;
        for (int j = 0; j < pl + 1; j++)
        {
            if (p[j] == '*' && j - 2 >= 0)
            {
                dp[0, j] = dp[0, j - 2];
            }
        }
        for (int i = 1; i < sl + 1; i++)
        {
            for (int j = 1; j < pl + 1; j++)
            {
                switch (p[j])
                {
                    case '*':
                        if (s[i] == p[j - 1] || p[j - 1] == '.')
                        {
                            dp[i, j] = dp[i - 1, j] || dp[i, j - 2];
                        }
                        else
                        {
                            dp[i, j] = dp[i, j - 2];
                        }
                        break;
                    case '.':
                        dp[i, j] = dp[i - 1, j - 1];
                        break;
                    default:
                        if (s[i] == p[j])
                        {
                            dp[i, j] = dp[i - 1, j - 1];
                            break;
                        }
                        break;
                }
            }
        }
        return dp[sl, pl];
    }
}

这里为了简化实现,就额外在s和p前加了个特殊字符’+’,没有什么含义,只是为了让代码更简洁一些,C#默认初始化数组采用类型默认值,bool类型默认值就是false,因此这里只把赋值为true的情况写了出来,同样是为了简化代码。

以s=”abaab”,p=”caba.*b”为例,打表如下:

dpp+c*a*ba.*b
s0123456789
+0111
a111
b21
a311
a411
b511

留下评论

您的邮箱地址不会被公开。 必填项已用 * 标注

Captcha Code