My easy DP solution in Java


  • 0
    N

    class Solution {
    public boolean isMatch(String s, String p) {

        if(s.length() == 0 && p.length() == 0){
            return true;
        }
            
        if(s.length() > 0 && p.length() == 0){
            return false;
        }
        
    
        
        
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m+1][n+1];
        
        
        
        
    
        dp[0][0] = true;
        for(int j = 1; j <= n; j++){
            dp[0][j] = (p.charAt(j-1) == '*')? dp[0][j-1]:false;
        }
        
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                      
                char c1 = s.charAt(i-1);
                char c2 = p.charAt(j-1);
                
                if(c1 == c2 || c2 =='?'){
                    dp[i][j] = dp[i-1][j-1];
                }else if(c2 == '*'){
                    //0, 1, and multiple
                    int cur = i;
                    while(cur >= 0){
                        if(dp[cur][j-1]){
                            dp[i][j] = true;
                            break;
                        }
                        cur--;
                    }
                }
                
            }
        }
        
        return dp[m][n];
        
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.