class Solution { public boolean isMatch(String s, String p) { //Ques 36 , dp playlist int m = p.length() , n = s.length(); boolean dp[][] = new boolean[m+1][n+1]; //+1 for empty string //last cell will be true , else last row and last colomn will be false //traversing reversely for(int i = m ; i >=0 ; i--){ for(int j = n ; j>=0 ; j--){ //if last cell if(i == m && j== n) dp[i][j] = true; //if last row else if(i == m) dp[i][j] = false; //if last coloumn else if(j == n){ //and * check below if(p.charAt(i) == '*') dp[i][j] = dp[i+1][j]; //else outright false else dp[i][j] = false; } //for rest of the matrix else{ //if ? , or char are same then check diagonally right //else it stays false , which is by default if(p.charAt(i) == '?' || p.charAt(i) == s.charAt(j)) dp[i][j] = dp[i+1][j+1]; //if * in rest of the matrix check right and below else if(p.charAt(i) == '*') dp[i][j] = dp[i][j+1] || dp[i+1][j]; } } } // 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[0][0]; } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter