Q37 Regular Expression Matching - LeetCode 10
Mon Mar 27 2023 16:23:21 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
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];
}
}
content_copyCOPY
https://leetcode.com/problems/regular-expression-matching/
Comments