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

动态规划，把pattern预处理一下，*字符和前面的字符分成一组， 就可以开始了，dp[i][j],表示str的前i个字符和pat（处理后的数组）的前n组字符是否能匹配上

class Solution {
public:
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param str string字符串 
 * @param pattern string字符串 
 * @return bool布尔型
 */
bool match(string str, string pattern) {
    // write code here
    vector<string> pat;
    for (int i = 0; i < pattern.size(); i++) {
        string str = "";
        str += pattern[i];
        if (i + 1 < pattern.size() && pattern[i+1] == '*') {
            str += '*';
            i ++;
        }
        pat.emplace_back(str);
    }
    
    int size1 = str.size() + 1;
    int size2 = pat.size() + 1;
    
    vector<vector<bool>> dp(size1, vector<bool>(size2, false));
    dp[0][0] = true;
    for (int i = 1; i < size2; i++) {
        if (dp[0][i-1] ==true) {
            if (pat[i - 1].size() > 1) {
                dp[0][i] = true;
                continue;
            }
            dp[0][i] = false;
        }
    }
    
    for (int i = 1; i < size1; i++) {
        for(int j = 1; j <size2; j++) {
            char c = pat[j-1][0];
            if (pat[j-1].size() == 1) {
                // 单字匹配的情况
                if (dp[i-1][j-1] == true && (c == '.' || c == str[i-1])) {
                    dp[i][j] = true;
                } else {
                    dp[i][j] = false;
                }
            } else {
                // 多字匹配的情况
                if (dp[i][j-1]) {
                    // 如果去除掉自身也能匹配上，那直接就为true
                    dp[i][j] = true;
                } else if (c == '.' || c == str[i-1]) {
                    // 如果单字符匹配上了，就一直往前找能匹配上的字符，一直到去除掉这些字符也能匹配上即dp[k-1][j-1] == true
                    for (int k = i; k > 0; k --) {
                        if (str[k-1] != str[i-1] && c != '.') {
                            break;
                        }
                        if (dp[k-1][j-1] == true) {
                            dp[i][j] = true;
                            break;
                        }
                    }
                    
                } else {
                    dp[i][j] = false;
                }
            }
        }
    }
    return dp[size1-1][size2-1];
}
};