Java DP

通配符匹配

http://www.nowcoder.com/questionTerminal/e96f1a44d4e44d9ab6289ee080099322

主要是对*的处理, 并且这里的*和传统正则的*还不太一样

    public boolean isMatch(String s, String p) {
        char[] str= s.toCharArray();
        char[] ptr= p.toCharArray();

        boolean[][] dp = new boolean[p.length()+1][s.length()+1];

        dp[0][0]=true;
        for(int i=1;i<dp.length;++i){
            if(ptr[i-1] == '*'){
                dp[i][0] = dp[i-1][0];
            }
        }

        for(int i=1;i<dp.length;++i){
            for(int j=1;j<dp[0].length;++j){
                if(ptr[i-1] == str[j-1] || ptr[i-1] =='?'){
                    dp[i][j] = dp[i-1][j-1];
                }else if(ptr[i-1]=='*'){
                    //匹配0个 一个或者多个
                    dp[i][j] =dp[i-1][j] || dp[i-1][j-1]|| dp[i][j-1]  ;
                }
            }
        }
        return dp[p.length()][s.length()];
    }
全部评论
for(int i=1;i
点赞 回复 分享
发布于 2021-08-01 16:53

相关推荐

点赞 评论 收藏
分享
lllllkin:感觉可以精简到一页简历,有些排版感觉不是必须的。 时间线越早的,你自己越熟悉的放前面。描述可以更精简些,一些问题解决感觉可以不用写具体技术栈,卖个关子,等面试官问。
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-01 11:47
点赞 评论 收藏
分享
评论
4
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务