Java DP solution 5ms


  • 0
    G
    public class Solution {
        public boolean isMatch(String s, String p) {
    	char[] cs = s.toCharArray();
    	char[] cp = p.toCharArray();		
    	int sLen = s.length();
    	int pLen = p.length();
    		
    	boolean[][] dp = new boolean[sLen+1][pLen+1];
    	dp[0][0] = true;
    		
    	for (int i = 0; i < pLen; i++) {
    	   if (cp[i] == '*' && dp[0][i-1]) {
                dp[0][i+1] = true;
              }
    	}
    	
    	for (int i = 1; i <= sLen; i++) {
    		for (int j = 1; j <= pLen; j++) {
    			if (cp[j-1] == cs[i-1] || cp[j-1] == '.') {
    				dp[i][j] = dp[i-1][j-1];
    			} else if (cp[j-1] == '*') {
    			 if (j <= 1) {
    				dp[i][j] = false;
    			 } else if (cp[j-2] != cs[i-1] && cp[j-2] != '.') {
                                         dp[i][j] = dp[i][j-2];
    			} else {
                                      dp[i][j] = (dp[i-1][j] || dp[i][j-1] || dp[i][j-2]);
           		        }
                         }
    		}			
    	}
    	return dp[sLen][pLen];
        }
    }
    

Log in to reply
 

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