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

官方题解的 js 版，以及个人理解的详细注释

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param str string字符串 
 * @param pattern string字符串 
 * @return bool布尔型
 */
function match( str ,  pattern ) {
    // write code here
    const m = str.length, n = pattern.length;
    // 1. dp 下标的含义
    // dp[i][j] 表示从 str 首字母到 i ，以及从 pattern 首字母到 j 的子字符串是否匹配
    // 只要存在 i = m - 1 时，有一个 j 为 true 即匹配
    const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(false));
    // 2. 初始化
    dp[0][0] = true;    // '' 和 '' 是匹配的
    // str 为 '' ，初始化 pattern 不为空串的情况
    // 例如：
    // '' 与 a* 这种情况时，dp[0][2] = true;
    // 这里从 2 开始，因为如果从 1 开始，即使 1 的位置是 '*' 也是无意义的，因为 * 和空串不匹配
    for(let i = 2; i <= n; i++) {   
        if(pattern[i - 1] === '*') dp[0][i] = dp[0][i - 2];
    }
    // 3. 状态转移
    // 状态转移时只需要分别考虑 '*' 和 其他字符时的情况
    // 其中 '*' 因为表示 0 次或者多次，需要特别注意 0 次的情况
    for(let i = 1; i <= m; i++) {
        for(let j = 1; j <= n; j++) {
            if(pattern[j - 1] !== '*') {    // 非 '*' 的情况
                if((pattern[j - 1] === '.' || pattern[j - 1] === str[i - 1])) {
                    // 如果当前两字符相同 或者 模式字符串指向字符为 '.'
                    // 则 dp[i][j] 是否匹配取决于前一个字符
                    dp[i][j] = dp[i - 1][j - 1] 
                }
            } else if(j >= 2) {    // '*' 的情况，这里 j 限定了 >=2 与初始化的意思是一致的
                 // 如果 '*' 前一个字符为 '.' 或者 '*' 的前一个字符与当前字符相同
                if(pattern[j - 2] == '.' || pattern[j - 2] === str[i - 1]) {   
                    // `有 i - 1 这个字符` 时，取决于 '*' 的前一个位置是否匹配
                    // 或，`没有 i - 1 这个字符` 时是否匹配
                    dp[i][j] = dp[i][j - 2] || dp[i - 1][j]; 
                } else {
                    // 如果 '*' 前面的字符 j - 1 与 i - 1 位置指向字符不同，或者不为 '.'
                    // 则，当前位置 dp[i][j] 是否匹配
                    // 取决于 `没有 j - 1 这个字符` 时的情况，也就是 dp[i][j - 2] 没有 j - 1 字符的状态
                    dp[i][j] = dp[i][j - 2];
                }
            }
        }
    }
    // 返回整个子串的匹配情况
    return dp[m][n];
}
module.exports = {
    match : match
};