LeetCode 10. 正则表达式匹配

发表于 | 更新于 | 分类于

题意

实现一个支持.和*的正则表达式匹配。其中.匹配任意单个字符，*匹配0或多个前面的那一个元素。

给出两个字符串s和p，前者只包含从a-z的小写字母，后者只包含从a-z的小写字母和两个匹配字符，问是否匹配。

思路

  • 想法0： 直接return regex_match(s, regex(p));
  • 想法1： 如果没有*，那直接写就可以了。其实多的*这个符号，无非就是将前一个字符变为了0道多个，通过递归枚举每种情况，轻松解决。时间复杂度：很大。
  • 想法2： 因为想法1的实现出现了重叠子问题，所以可以通过DP来进行优化。
    具体操作：用p[i][j]表示s串[0,i]与p串[0,j]匹配的结果。
    1. s[i] == p[j] || p[j] == '.'时，dp[i][j] = dp[i-1][j-1]。
    2. s[i] != p[j]时，可能发生匹配的情况只有p[j] == '*'，此时所有可能如下：
      • *前的字符与对应位置字符无法匹配，此时只能使其出现0次才可继续匹配，即dp[i][j] = dp[i][j - 2]。
      • *前的字符与对应位置字符可匹配，此时*可以匹配多个、1个或0个，即dp[i][j] = dp[i - 1][j] || dp[i][j - 1] || dp[i][j - 2]。
    3. 无法匹配时的情况不用再讨论了，因一开始dp数组就都初始化为了0。

代码

  • 代码0：

    1
    2
    3
    4
    5
    6
    class Solution {
    public:
        bool isMatch(string s, string p) {
            return regex_match(s, regex(p));
        }
    };

  • 代码1：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    class Solution {
    public:
        bool isMatch(string s, string p) {

            if(p.size() == 0)   return s.size() == 0;

            bool first = (s.size() && (s[0] == p[0] || p[0] == '.'));
            if(p.size() >= 2 && p[1] == '*')
                return isMatch(s, p.substr(2)) || (first && isMatch(s.substr(1), p));
            else
                return first && isMatch(s.substr(1), p.substr(1));

        }
    };

  • 代码2：

    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
    class Solution {
    public:
        bool isMatch(string s, string p) {

            int lens = s.size(), lenp = p.size();
            bool dp[lens + 1][lenp + 1];

            for(int i = 0; i <= lens; ++i)
                for(int j = 0; j <= lenp; ++j)
                    dp[i][j] = 0;

            dp[0][0] = 1;
            if(lenp > 1)
            {
                for(int i = 1; i < lenp; i += 2)
                    if(p[i] == '*')
                        dp[0][i + 1] = dp[0][i - 1];
            }
            for(int i = 1; i <= lens; ++i)
            {
                for(int j = 1; j <= lenp; ++j)
                {
                    if(s[i - 1] == p[j - 1] || p[j - 1] == '.')
                        dp[i][j] = dp[i - 1][j - 1];
                    else if(j > 1 && p[j - 1] == '*')
                    {
                        if(p[j - 2] != s[i - 1] && p[j - 2] != '.')
                            dp[i][j] = dp[i][j - 2];
                        else
                            dp[i][j] = dp[i - 1][j] || dp[i][j - 1] || dp[i][j - 2];
                    }
                }
            }
            return dp[lens][lenp];
        }
    };

总结

DP是很优美的思路，关键在于建立状态转移方程，多加练习可培养。

Donate comment here
0%