[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;
                    dp[i][j] |=(dp[i-1][j]&&(schar[i-1]==pchar[j-2]||pchar[j-2]=='.'))
                    else if(pchar[j-1]=='.' || pchar[j-1]==schar[i-1]) 
            return dp[slen][plen];

  • 0

    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.