8 Line Java Solution using DP


  • 0
    N
    public boolean isMatch(String s, String p) {
            boolean[][] dp = new boolean[s.length()+1][p.length()+1];
            dp[0][0] = true;
            for(int i=0;i<=s.length();i++)
                for(int j=1;j<=p.length();j++){
                    if(p.charAt(j-1) == '*')  dp[i][j] = dp[i][j-1]||(i>0&&(dp[i-1][j]||dp[i-1][j-1]));
                    else    dp[i][j] = (i>0&&dp[i-1][j-1]) && (p.charAt(j-1)=='?'||(i>0&&p.charAt(j-1)==s.charAt(i-1)));
                }
            return dp[s.length()][p.length()];
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.