concise java DP code with detail explanation, very easy to understand


  • 0
    B
    /**
     * M[i][j] represents that if first i character from s and first j character from p could match
     * base case: M[0][0] = true;
     * Induction rule: case 1: p[j - 1] == '?' then M[i][j] = M[i - 1][j - 1]
     *                 case 2: P[j - 1] == S[i - 1] then M[i][j] = M[i - 1][j - 1]
     *                 case 3: P[j - 1] = '*' then M[i][j] = M[i][j - 1](this means '*' serve as empty) || M[i - 1][j]
     *                 other case: false, so we just ignore them
     *
     */
    

    hope it helps : )

    public class Solution {   
        public boolean isMatch(String s, String p){
            boolean[][] M = new boolean[s.length() + 1][p.length() + 1];
            M[0][0] = true;
            for (int i = 0 ; i <= s.length() ; i++){
                for (int j = 0 ; j <= p.length() ; j++){
                    if (i == 0 && j == 0){
                        continue;
                    }
                    if (i >= 1 && j >= 1 && (p.charAt(j - 1) == '?' || p.charAt(j - 1) == s.charAt(i - 1))){
                        M[i][j] = M[i][j] || M[i - 1][j - 1];
                    }else if (j >= 1 && p.charAt(j - 1) == '*'){
                        M[i][j] = M[i][j] || M[i][j - 1];
                        if (i - 1 >= 0){
                            M[i][j] = M[i][j] || M[i - 1][j];
                        }
                    }
                }
            }
            return M[s.length()][p.length()];
        }
    }
    

Log in to reply
 

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