Leetcode|线性序列|10. 正则表达式匹配（两字符串前均补1个相同字符）

s = " " + s;
p = " " + p;

class Solution {
public:
    bool isMatch(string s, string p) {
        // 判断"*"是否匹配需已知前2位，所以在两字符串前同补相同字符
        s = " " + s;
        p = " " + p;
        int asize = s.size();
        int bsize = p.size();
        // 通用初始化
        vector<vector<int>> dp(asize + 1, vector<int>(bsize + 1, false));
        // 边界初始化
        dp[0][0] = true;
        for (int i = 1; i <= asize; i++)
            for (int j = 1; j <= bsize; j++) {
                // 1.若两字符相同(或遇"."通配符)则两索引同步后移1位
                if (s[i - 1] == p[j - 1] || p[j - 1] == '.')
                    dp[i][j] = dp[i - 1][j - 1];
                // 2.若两字符不同是因为遇到"*"通配符
                else if (p[j - 1] == '*') {
                    // 2.1 "*"通配符前1位字符与s字符相同 -> (0次 || 多次匹配)
                    if (s[i - 1] == p[j - 2] || p[j - 2] == '.')
                        dp[i][j] = dp[i][j - 2] || dp[i - 1][j];
                    // 2.2 "*"通配符前1位字符与s字符不同 -> 0次匹配
                    else dp[i][j] = dp[i][j - 2];
                }
            }
        return dp[asize][bsize];
    }
};