LeetCode 10. 正则表达式匹配

LeetCode 10. 正则表达式匹配

动态规划

const int N = 25, M = 35;
class Solution {
public:
    bool f[N][M] = {false}; // s前i与p前j匹配
    bool isMatch(string s, string p) {
        int n = s.size(), m = p.size();
        s = " " + s, p = " " + p; 
        
        // 初始化条件，只有最后一个字符是*时才可能匹配
        f[0][0] = true;
        for(int i = 1; i <= m; i ++)
            if(p[i] == '*')
                f[0][i] = f[0][i - 2];

        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= m; j ++)
            {
                if(j + 1 <= m && p[j + 1] == '*') continue;
                if(p[j] != '*')  //不是*并且匹配
                    f[i][j] = f[i - 1][j - 1] &&(s[i] == p[j] || p[j] == '.');
                if(p[j] == '*') //是*，并且分为代表1个字符，两个字符，三个字符....
                    f[i][j] = f[i][j - 2] || f[i - 1][j] && (s[i] == p[j - 1] || p[j - 1] == '.');
            }
        return f[n][m];
    }
};
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