Need a unique gift idea?
A Pastebin account makes a great Christmas gift
SHARE
TWEET

Untitled

a guest Dec 15th, 2017 49 Never
Upgrade to PRO!
ENDING IN00days00hours00mins00secs
 
  1. class Solution {
  2.        public boolean isMatch(String s, String p) {
  3.         int m=s.length(), n=p.length();
  4.     boolean[][] dp = new boolean[m+1][n+1];
  5.     dp[0][0] = true;
  6.            
  7.     //whole column false
  8.     for (int i=1; i<=m; i++) {
  9.         dp[i][0] = false;
  10.     }
  11.     // first k stars must be true
  12.     for(int j=1; j<=n; j++) {
  13.         if(p.charAt(j-1)=='*'){
  14.             dp[0][j] = true;
  15.         } else {
  16.             break;
  17.         }
  18.     }
  19.    
  20.     for(int i=1; i<=m; i++) {
  21.         for(int j=1; j<=n; j++) {
  22.             if (s.charAt(i-1)==p.charAt(j-1) || p.charAt(j-1)=='?') {
  23.                 dp[i][j] = dp[i-1][j-1];
  24.             } else if (p.charAt(j-1)=='*') {
  25.                 dp[i][j] = dp[i-1][j] || dp[i][j-1];
  26.             } else
  27.                 dp[i][j] = false;
  28.         }
  29.     }
  30.     return dp[m][n];
  31.            
  32.     }
  33. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top