class Solution { public boolean isMatch(String s, String p) { //Ques 36 , dp playlist int m = p.length() , n = s.length(); //2nd approach (recursion + memoization) //in 1 based indexing // return solve(s , p , m , n , new Boolean[m+1][n+1]); //tabulization boolean dp[][] = new boolean[m+1][n+1]; //base case dp[0][0] = true; for(int j = 1 ; j <= n ;j++) dp[0][j] = false; for(int i = 1; i <= m ; i++){ boolean flag = true; for(int ii = 1; ii <= i ; ii++){ if(p.charAt(ii - 1) !='*'){ flag = false; break; } } dp[i][0] = flag; } for(int i = 1 ; i <= m ; i++){ for(int j = 1 ; j<= n ;j++){ char ch1 = p.charAt(i-1), ch2 = s.charAt(j-1); if(ch1 == ch2 || ch1 == '?'){ dp[i][j] = dp[i-1][j-1]; } else if(ch1 == '*') dp[i][j] = dp[i-1][j] || dp[i][j-1]; else dp[i][j] = false; } } return dp[m][n]; } public boolean solve(String s , String p , int i , int j , Boolean[][] dp){ if(i ==0 && j == 0) return true ; //both exhausted == matched if(i == 0 && j > 0) return false; //j remains //if s remains and its all * if(i > 0 && j == 0){ for(int ii = 1 ;ii <=i ; ii++){ if(p.charAt(ii-1) != '*' ) return false; } return true; } if(dp[i][j] != null) return dp[i][j]; char ch1 = p.charAt(i-1), ch2 = s.charAt(j-1); if(ch1 == ch2 || ch1 == '?'){ return dp[i][j] = solve(s,p , i-1 , j-1 , dp); } //keeping * as emptry string and making a call to next char //keeping * as that character and making call for next char with another * else if(ch1 == '*') return dp[i][j] = solve(s ,p ,i-1 ,j , dp) || solve(s, p , i, j-1 , dp); //if chars are not equal return dp[i][j] = false; } }
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