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

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */
    bool match(string str, string pattern) {
        int n1 = str.length();
        int n2 = pattern.length();
        vector<vector<bool>> dp(n1+1, vector<bool>(n2+1, false));
        dp[0][0]=true;
        for (int i=2; i<=n2; i++){
            if (pattern[i-1] == '*')
            dp[0][i] = dp[0][i-2];
        }
        for (int i=1; i<=n1; i++){
            for (int j=1; j<=n2; j++){
                if (pattern[j-1]=='.'||pattern[j-1]==str[i-1]){
                    dp[i][j] = dp[i-1][j-1];
                } else if (pattern[j-1]=='*'){
                    if (pattern[j-2]=='.'||pattern[j-2]==str[i-1]){
                        dp[i][j] = dp[i-1][j]||dp[i][j-2];
                    }
                    else dp[i][j] = dp[i][j-2];
                }
            }
        }
        return dp[n1][n2];
    }
};

初始化dp数组：

1. dp[0][0]=true 因为空的str和空的pattern匹配。
2. 当str长度为0，pattern中有*出现，则可以忽略（字母*）这两个字符，也能匹配空的str。

分情况（设pattern当前字符位=j-1，str当前字符位为i-1）：

1. pattern当前字符位为'.', 或pattern当前位与str当前位匹配：取决于这一位之前两者是否完全匹配
2. pattern当前字符位为'*', 分两种情况：
1. pattern的‘*’前一位为‘.’，或与str当前位匹配：可以是匹配一个或多个str中的该字符，也可以是0个
1. pattern的‘*’前一位与str不匹配，则pattern中的（字母*）不匹配str中的任何东西，忽略

3. pattern当前位不是特殊字符‘*’或‘.’而且与str当前位不匹配，则确定不匹配，因为数组初始值为false，故这种情况在代码中直接不用处理。