动态规划两个数组dp问题系列一＞通配符匹配

用户11305962

发布于 2025-02-09 22:06:55

4300

代码可运行

文章被收录于专栏：学习

运行总次数：0

代码可运行

状态表示：

状态转移方程：

初始化：

填表顺序：

返回值：

返回dp[m][n]

代码：

class Solution {
    public boolean isMatch(String ss, String pp) {
        int m = ss.length(); int n = pp.length();
        ss = " "+ss;
        pp = " "+pp; 
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();
        boolean[][] dp = new boolean[m+1][n+1];

        //初始化：
        dp[0][0] = true;
        for(int i = 1; i <= n; i++){
            if(p[i] == '*') dp[0][i] = true;
            else break;
        }

        //填表：
        for(int i = 1; i <= m; i++)
            for(int j = 1; j <= n; j++){
                if(p[j] == '*') 
                    dp[i][j] = dp[i-1][j] || dp[i][j-1];
                else 
                    dp[i][j] = (p[j] == '?' || p[j] == s[i]) && dp[i-1][j-1];
            } 

        return dp[m][n];    
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-02-08，如有侵权请联系 cloudcommunity@tencent.com 删除

boolean