0%

正则表达式匹配

发表于 更新于

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

  1. 词法：状态机
  2. dp[m, n]指模式p[0,m]与字符串s[0,n]匹配

dp[m,n]={trueif m=0 and n=0falseif m=0 and n≠0dp[m−2,n] or dp[m−1,n] ordp[m−1,n−1] and(p[m−1]=s[n] or p[m−1]=′.′)if m≥1 and p[m]=′∗′dp[m−1,n−1] and (p[m]=s[n] or p[m]=‘‘.")otherwisedp[m, n] = \begin{cases} true & if\ m=0 \ and\ n=0 \\ false & if\ m=0 \ and\ n \neq 0 \\ dp[m - 2, n]\ or\ dp[m - 1, n]\ or\\ \quad dp[m - 1, n - 1]\ and\\ \qquad (p[m - 1] = s[n]\ or\ p[m - 1] = '.') & if\ m \ge 1\ and\ p[m]='*' \\ dp[m - 1, n - 1]\ and\ (p[m] = s[n]\ or\ p[m]=``.") & otherwise \end{cases}

dp[m, n]仅仅与dp[m - 2, n], dp[m - 1, n], dp[m - 1, n - 1]有关

或，倒推，dp[m, n]指模式p[m:]与字符串s[n:]匹配

dp[m,n]={trueif m=len(p) and n=len(s)falseif m=len(p) and n≠len(s)dp[m+2,n] or (p[m]=s[n] or p[m]=′.′) and (dp[m+2,n+1] or dp[m,n+1])if m<len(p) and p[m+1]=′∗′dp[m+1,n+1] and (p[m]=s[n] or p[m]=′.′)otherwisedp[m, n] = \begin{cases} true & if\ m = len(p) \ and\ n = len(s) \\ false & if\ m = len(p) \ and\ n \neq len(s) \\ dp[m + 2, n]\ or\ (p[m] = s[n]\ or\ p[m] = '.') \\ \quad \ and\ (dp[m + 2, n + 1]\ or\ dp[m, n + 1]) & if\ m \lt len(p)\ and\ p[m + 1] = '*' \\ dp[m + 1, n + 1]\ and\ (p[m] = s[n]\ or\ p[m]='.') & otherwise \end{cases} 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
// 注：以下程序在GCC及Clang++ 3.x下，用例"a","a."中行为异常，在Clang++更高版本中没有问题
class Solution {
public:
    bool match(const char* str, const char* pattern)
    {
        if (str == nullptr || pattern == nullptr)
        {
            return false;
        }
        else
        {
            const int sl = strlen(str);
            const int pl = strlen(pattern);
            if (sl != 0 && pl == 0)
            {
                return false;
            }
            else
            {
                bool dp[sl + 1][pl + 1];
                memset(dp, false, sizeof(dp));
                dp[sl][pl] = true;
                for (int i = sl; i >= 0; i--)
                {
                    for (int j = pl - 1; j >= 0; j--)
                    {
                        if (j == pl - 1)
                        {
                            if (pattern[j] == str[i] || pattern[j] == '.')
                            {
                                dp[i][j] = dp[i + 1][j + 1];
                            }
                            else
                            {
                                dp[i][j] = false;
                            }
                        }
                        else
                        {
                            if (pattern[j + 1] == '*')
                            {
                                if (dp[i][j + 2])
                                {
                                    dp[i][j] = true;
                                }
                                else
                                {
                                    if (pattern[j] == str[i] || pattern[j] == '.')
                                    {
                                        if (i == sl)
                                        {
                                            dp[i][j] = dp[i][j + 2];
                                        }
                                        else
                                        {
                                            dp[i][j] =  (dp[i + 1][j + 2] || dp[i + 1][j]);
                                        }
                                    }
                                    else
                                    {
                                        dp[i][j] = false;
                                    }
                                }
                            }
                            else
                            {
                                if (pattern[j] == str[i] || (pattern[j] == '.' && str[i] != '\0'))
                                {
                                    dp[i][j] = dp[i + 1][j + 1];
                                }
                                else
                                {
                                    dp[i][j] = false;
                                }
                            }
                        }
                    }
                }
                return dp[0][0];
            }
        }
    }
};