Q37 Regular Expression Matching - LeetCode 10

PHOTO EMBED

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/