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

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */
    
    /*
        par   ...     j-2               j-1
        str   ...     i-2               i-1
        dp    ...     [i-1, j-1]        [i,j]
    */

    // 注意：
    // . 可以匹配任何字符   ， * 前面字符个数可为零；因此，很多情况得考虑上上个结果
    bool match(string str, string pattern) {
        // write code here
        // 使用dp[i][j] 表示str的前i个字符和pattern的前j个字符匹配
        int n1 = str.size();
        int n2 = pattern.size();
        vector<vector<bool>> dp(n1+1, vector<bool>(n2+1, false));

        dp[0][0] = true;    // 匹配对象都为零时，表示匹配成功，直接赋值为true
        for(int j = 2; j <= n2; ++j)
        {
            if(pattern[j-1] == '*')         // * 存在上一个字母出现次数为0情况，因此，
                dp[0][j] = dp[0][j-2];      // 当前情况的匹配与否更多看上上个情况
        }
        for(int i = 1; i <= n1; ++i)
        {
            for(int j = 1; j <= n2; ++j)
            {   
                // 不为 * 情况,只能匹配时当前才会true，因此整体情况看上一次匹配情形
                if(pattern[j-1] != '*' && (pattern[j-1] == '.' || pattern[j-1] == str[i-1])){
                    dp[i][j] = dp[i-1][j-1];
                }
                else if ( j >= 2 && pattern[j-1] == '*')    // 为*情况
                {
                    if(pattern[j-2] == '.' || pattern[j-2] == str[i - 1])   // 若 . 则表示可以任意匹配，因此只能看模版上上次情况；若匹配上了，则看看上一次原来的匹配情况
                        dp[i][j] = dp[i][j-2] || dp[i-1][j];
                    else
                        dp[i][j] = dp[i][j-2];  // * 表示前面字符出现次数为0，则表示当前匹配情况看上上次情况
                }
            }
        }
        return dp[n1][n2];//所有匹配情况，都会汇集到最后一个结果
    }
};