DP数组应该保存什么?

两个字符串应该考虑使用二维DP数组，题目所求的是字符串str是否匹配模式串pattern，则dp[i][j]应该保存字符串从开头到第i个字符的子串匹配模式串从开头到第j个字符的子串的情况，如果不匹配保存false，匹配则保存true。（保存布尔值的DP数组在进行状态转移时可能要和前面的状态进行与或非的运算）

最小子问题

  • 当模式串和字符串都为空串时，两者匹配：dp[0][0] = true
  • 当模式串为空串，字符串不为空串时，两者必不匹配：dp[i][0] = false
  • 当模式串不为空串，字符串为空串时，两者是否匹配要考虑*字符，如果出现*字符，那*字符的前面一个字符只有出现0次才可能和空串匹配，此时dp[0][j] = dp[0][j-2]

如何思考状态转移方程？

二维dp数组问题一般考虑两个字符串的当前字符的情况，设当前处理到字符串str的第i个字符和模式串pattern的第j个字符，两个字符串当前字符有以下情况：

  • 两个字符串的当前位置的字符匹配，即str[i-1] == pattern[j-1]或者pattern[j-1] == "."，此时两个字符串是否匹配则取决于前一位置的子串是否匹配，即dp[i][j] = dp[i-1][j-1]
  • 两个字符串当前字符为"*"，由于"*"表示前面的字符可以出现0次或多次，因此要结合出现0次和多次的情况判断是否匹配
  • 如果"*"前面的字符出现多次，则此时只有str的当前字符和pattern的前一个字符相等时才有可能整个子串匹配，dp[i][j] = (str[i-1] == pattern[j-2] || pattern[j-2] == ".") && dp[i][j] = dp[i-1][j]
  • 如果"*"前面的字符出现0次，此时模式串中的*和前一个字符不参与匹配，两个子串匹配情况取决于模式串去掉*和前一个字符后的子串和当前str子串的匹配情况，dp[i][j] = dp[i][j-2]

前面两种情况要结合起来判断，因此要用||号连接。

参考

https://blog.nowcoder.net/n/72a4b64ed44f43359d41959f1c8d5769?f=comment

https://blog.nowcoder.net/n/a3d770a390da4683aa6e6a9020d59945?f=comment

**********************************************************************

/*
 * @Author: LibraStalker **********
 * @Date: 2023-04-13 10:47:58
 * @FilePath: BM76-正则表达式匹配.js
 * @Description: 
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param str string字符串 
 * @param pattern string字符串 
 * @return bool布尔型
 */
function match( str ,  pattern ) {
    // write code here
    const dp = Array.from(new Array(str.length+1), () => new Array(pattern.length+1).fill(false));

    // 初始状态
    dp[0][0] = true;
    for (let j = 2; j <= pattern.length; ++j) {  // 字符串为空，模式不为空的情况，第一位不可能为*，所以从j从2开始
        if (pattern[j-1] === "*") {  // 如果当前字符为*，则前面一个字符可以出现0次实现空串，此时是否匹配则看pattern除了*和前一位字符之前的模式是否能匹配当前串
            dp[0][j] = dp[0][j-2];
        }
    }

    for (let i = 1; i <= str.length; ++i) {
        for (let j = 1; j <= pattern.length; ++j) {
            if (str[i-1] === pattern[j-1] || pattern[j-1] === ".") {  // 当前字符匹配，则此当前子串和当前子模式是否匹配取决于这一字符前的子串和模式是否匹配
                dp[i][j] = dp[i-1][j-1];
            }
            else if (pattern[j-1] === "*"  && j >= 2) {  // *只能从模式的第二位开始出现
                if (str[i-1] === pattern[j-2] || pattern[j-2] === ".") {  // *前面的字符出现多次的情况：如果str当前字符和pattern上一个字符一致，则当前位置匹配情况取决于str上一位置和当前pattern的匹配情况
                    dp[i][j] = dp[i-1][j];
                }
                dp[i][j] |= dp[i][j-2];  // *前面的字符出现0次的情况：上面是匹配多次的情况，但如果*前面的字符出现0次跟str不匹配，那当前模式还是不能匹配当前字符串，所以要用|结合这两种情况判断
            }
        }
    }

    return dp[str.length][pattern.length];
}

match("aaa","aa*");
module.exports = {
    match : match
};