题解 | 正则表达式匹配

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param str string字符串
 * @param pattern string字符串
 * @return bool布尔型
 */
function match(str, pattern) {
    // write code here
    const m = pattern.length;
    const n = str.length;
    // 用当前正则去匹配空字符串
    const dp = Array.from({ length: m + 1 }, () =>
        new Array(n + 1).fill(false)
    );

    // str 是空字符串的时候
    dp[0][0] = true;
    for (let i = 1; i <= m; i++) {
        // .*可以匹配任意个，也可以匹配空字符串
        if (pattern[i - 1] === "*") {
            dp[i][0] = dp[i - 2][0];
        }
    }
    // pattern 是空字符串的时候，都是false
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            // 可以匹配0个或者多个
            if (pattern[i - 1] === "*") {
                dp[i][j] = dp[i - 2][j]; // 匹配0个

                // 匹配1个至多个
                let l = j;
                // l位置就是匹配到的，l和i -1 位置匹配到了，就需要取得dp[i - 2][l - 1]的结果
                // 就需要获取pattern[i - 2]位置的字符和str[l - 1]位置的字符是否匹配
                while (
                    (pattern[i - 2] === '.' || pattern[i - 2] === str[l - 1]) 
                    && l > 0
                ) {
                    dp[i][j] = dp[i][j] || dp[i - 2][l - 1];
                    if (dp[i][j]) break;
                    l--;
                }
                // . 可以匹配任意字符
            } else if (pattern[i - 1] === "." || pattern[i - 1] === str[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            }
        }
    }
    console.log(dp)
    return dp[m][n];
}
module.exports = {
    match: match,
};