Q34 Wildcard Matching - LeetCode 44

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;
        
    }   
}