LeetCode 44通配符匹配：递归DP代码在s="aa",p="*"测试用例失败求分析

针对测试用例s="aa"、p="*"执行失败的问题，代码存在以下核心错误：

1. 字符与字符串的错误比较 #

代码中多处使用p.charAt(j) + "" == "*"或p.charAt(j) + "" == "?"判断通配符，这是对象引用比较而非内容比较。p.charAt(j) + ""会创建新的String对象，而字面量"*"在字符串常量池中，两者用==比较会返回false，直接导致通配符的判断逻辑完全失效。

比如测试用例中p="*"，j=0时，p.charAt(j) + "" == "*"结果为false，代码不会进入*的处理分支，直接走到最后返回false，这是测试用例失败的直接原因。

2. DP数组的无效赋值 #

由于通配符判断失效，代码遇到*时无法执行正确的递归逻辑，错误地将dp[i][j]赋值为0，后续递归调用会复用这个错误的缓存结果，进一步放大问题。

修正后的代码 #

将所有字符串比较改为字符直接比较（char是基本类型，用==即可），修正后的代码如下：

import java.util.Arrays;

class Solution {
    public boolean isMatch(String s, String p) {
        int n = s.length();
        int m = p.length();
        int[][] dp = new int[n][m];
        for(int[] it : dp)
            Arrays.fill(it, -1);
        return solve(n-1 , m-1, s ,p , dp);
    }
    
    public boolean solve(int i, int j, String s, String p, int[][] dp){
        if(i < 0 && j < 0) return true;
        if(i < 0 && j >=0){
            while(j>=0){
                if(p.charAt(j) == '*') j--;
                else return false;
            }
            return true;
        }
        if(j < 0 && i >=0) return false;
        if(dp[i][j] != -1){
            return dp[i][j] == 1;
        }
        if(s.charAt(i) == p.charAt(j) || p.charAt(j) == '?'){
            boolean temp = solve(i-1,j-1,s,p,dp);
            dp[i][j] = temp ? 1 : 0;
            return temp;
        }  
        if(p.charAt(j) == '*'){
            boolean temp = solve(i-1,j,s,p,dp) || solve(i,j-1,s,p,dp);
            dp[i][j] = temp ? 1 : 0;
            return temp;
        }
        dp[i][j] = 0;
        return false;
    }
}

其他优化说明 #

• 简化了dp数组的取值判断，直接返回dp[i][j] == 1，去除冗余的if-else分支。
• *的处理逻辑本身是正确的：solve(i-1,j)表示*匹配当前字符并继续匹配后续字符，solve(i,j-1)表示*匹配空字符，两者取或即可覆盖所有可能的匹配场景。

内容的提问来源于stack exchange，提问作者Pratham Kapoor