题目描述

Given an input string (s) and a pattern (p), implement regular expression matching with support for ‘.’ and ‘*’.

’.’ Matches any single character.
‘*’ Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

Note:

s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like . or *.

算法1

DP $O(m * n)$

C++ 代码

    // 为处理方便， s=" " +s, p=" " + p
    // d[i][j]: s[0..i] 与 p[0..j] 是否匹配?

    // d[i][j] = if s[i]==p[j] || p[j] == '.': d[i-1][j-1]
    // else :  if p[j] == '*':  匹配0个，d[i][j-2]； 匹配多个: d[i-1][j]

    // init: d[0][0] = true
    //  for i=1..m: d[i][0] = false;                    // s = " abc", p=" "
    //  for j=1..n: d[0][j] = p[j]=='*' && d[0][j-2]    // s = " ", only p = " .*.*.*" is true

    bool isMatch(string s, string p) {
        s = " " + s;
        p = " " + p;
        int m = s.size(), n = p.size();

        vector<vector<int>> f(m, vector<int>(n, 0));

        // init
        f[0][0] = true;
        for(int i=1; i<m; i++) f[i][0] = false;
        for(int j=1; j<n; j++) f[0][j] = p[j]=='*' && f[0][j-2];

        for(int i=1; i<m; i++) {
            for(int j=1; j<n; j++) {
                if( s[i] == p[j] || p[j] == '.' ) f[i][j] = f[i-1][j-1];
                else {
                    f[i][j] = p[j]=='*' 
                        && ( f[i][j-2] // 吃掉0个
                            || (( p[j-1]=='.' || p[j-1]==s[i]) && f[i-1][j]) ); // 吃掉1个
                }
            }
        }
        return f[m-1][n-1];
    }