LeetCode 题解——Regular Expression Matching

发表于 | 分类于 | 阅读次数:
字数统计: 532 字

LeetCode 题解——Regular Expression Matching

题意

实现支持.和*正则匹配

题解

一开始的想法是从左向右进行模拟匹配，模拟的代码比较长，后面遇到这种情况：

1
2
aaa
a*a

就行不通了

事实上，上面那种情况的我们在匹配a*的时候，要分是否匹配a这个东西分两种情况进行讨论，这个时候就有一种递归的思路：
首先判断第一个字符是否匹配，然后判断是否是*模式，是的话可以匹配这个字符也可以不匹配，如果不是*模式的话就判断后面。

递归代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool isMatch(string s, string p) {
        int plen = p.size(), slen = s.size();
        if(plen == 0) return slen == 0;
        // 是否匹配第一个
        bool matchfirst = (slen != 0 && (s[0] == p[0] || p[0] == '.'));
        // 是否是*模式
        if(plen >= 2 && p[1] == '*')
            return (isMatch(s, p.substr(2)) || (matchfirst && isMatch(s.substr(1), p)));
        else
            return (matchfirst && isMatch(s.substr(1), p.substr(1)));
    }
};

这样的递归我们会发现有大量的重复调用，这个时候可以使用动态规划进行优化。
dp[i][j]表示isMatch(s.strsub(i), p.strsub(j))，由上面的递归方案我们可以推得

dp[i][j]=

  1. dp[i][j+2],当前为*模式时不匹配的情况
  2. dp[i+1][j],当前为*模式，并且第一个字符匹配成功的情况
  3. dp[i+1][j],非*模式，第一个字符匹配成功的情况

DP代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool isMatch(string s, string p) {
        int plen = p.length(), slen = s.length();
        vector<vector<bool> > dp(slen + 1, vector<bool> (plen + 1, false));
        dp[slen][plen] = true;
        for(int i=slen ;i>=0;--i)
        {
            for(int j=plen-1;j>=0;--j)
            {
                // 判断第一个是否匹配
                bool match = (i<slen && (s[i] == p[j] || p[j] == '.'));
                // 是*模式，两种方案，匹配/不匹配
                if(j+1 < plen && p[j+1] == '*')
                    dp[i][j] = dp[i][j+2] || (match && dp[i+1][j]);
                // 非*模式
                else
                    dp[i][j] = (match && dp[i+1][j+1]);
            }
        }
        return dp[0][0];
    }
};

更多LeetCode题解，欢迎查看我的GitHub项目