Q36 Wildcard Matching - LeetCode
Mon Mar 27 2023 10:09:19 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
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];
}
}
content_copyCOPY
https://leetcode.com/problems/wildcard-matching/
Comments