class Solution { public boolean isMatch(String s, String p) { //Q37 of dp playlist , int m = p.length() , n = s.length(); //pattern on rows , str on col boolean [][] dp = new boolean[m+1][n+1]; //for empty string //traversing the dp for(int i = 0 ; i < m+1 ; i++){ for(int j = 0 ; j< n+1 ; j++){ //if 0,0 ->true if(i == 0 && j== 0) dp[i][j] = true; //if first coloumn else if(j==0){ //if * check 2 rows above if(p.charAt(i-1) == '*') dp[i][j] = dp[i-2][j]; //if p.charAt(j) == any char or '.' it stays false } //first row all false else if(i==0) dp[i][j] = false; //rest of the string else{ //if chars are equal or . then check diagonally behind if(p.charAt(i-1)==s.charAt(j-1) || p.charAt(i-1) == '.') dp[i][j] = dp[i-1][j-1]; /* if * then check 2 rows above and also if last chars are equal then check left also , ans will be OR of both here last chars means char before * and last char of str char before * can also be '.' */ else if(p.charAt(i-1) == '*'){ dp[i][j] = dp[i-2][j]; if(p.charAt(i-2)==s.charAt(j-1) || p.charAt(i-2) == '.') dp[i][j] = dp[i][j] || dp[i][j-1]; } } } } // for(int i = 0 ; i < m+1 ; i++){ // for(int j = 0 ; j < n+1 ; j++) // System.out.print(dp[i][j] + " "); // System.out.println(); // } return dp[m][n]; } }