题解 | #正则表达式匹配#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */
    bool match(string str, string pattern) {
        // write code here
        int n = str.size();
        int m = pattern.size();
        vector<vector<bool>> f(n+1, vector<bool>(m+1, false)); // f[i][j]代表str前i个和pattern前j个匹配情况
        // 初始化
        f[0][0] = true;

        for(int i = 0; i <= n; i++) {
            for(int j = 0; j <= m; j++) {
                if(j != 0){
                    if(pattern[j - 1] != '*') {
                        if(i > 0 && (str[i-1] == pattern[j-1] || pattern[j-1] == '.'))
                            f[i][j] = f[i-1][j-1];
                    } else {
//                     if(f[i][j-1]) // 星号匹配一次
//                         f[i][j] = f[i][j-1];
                        if(j >= 2 && f[i][j-2]) // 星号匹配零次
                            f[i][j] = f[i][j-2];
                        else if(i >= 1 && j >= 2) // 星号匹配多次
                            f[i][j] = (f[i-1][j] && (str[i-1] == pattern[j-2] || pattern[j-2] == '.'));
                    }
                }
            }
        }
        return f[n][m];
    }
};