[JAVA 5ms] Elegant DP Solution


  • 0
    public class Solution {
        public boolean isMatch(String s, String p) {
            if(s==null || p==null) return false;
            int slen=s.length(), plen=p.length();
            char[] schar=s.toCharArray(), pchar=p.toCharArray();
            boolean[][] dp=new boolean[slen+1][plen+1];
            for(int i=0;i<=slen;i++){
                for(int j=0;j<=plen;j++){
                    if(i==0&&j==0) { dp[i][j]=true;continue;}
                    if(i==0) { dp[i][j]=pchar[j-1]=='*'&&dp[i][j-2];continue;}
                    if(j==0) continue;
                    
                    if(pchar[j-1]=='*'){
                    dp[i][j] |=(dp[i-1][j]&&(schar[i-1]==pchar[j-2]||pchar[j-2]=='.'))
                                ||dp[i][j-1]||dp[i][j-2];
                    }
                    else if(pchar[j-1]=='.' || pchar[j-1]==schar[i-1]) 
                            dp[i][j]=dp[i-1][j-1];
                }
            }
            return dp[slen][plen];
        }
    }
    

  • 0
    B

    33 ms test on Sep 20


Log in to reply
 

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