Problem 10 of LeetCode

q10.java

public class Solution {
    public boolean isMatch(String s, String p) {
        // m[i][j] means: does s[0..i-1] match p[0..j-1]?
        // where when i = 0, s[0..i-1] is the empty string.
        boolean[][] m = new boolean[s.length()+1][p.length()+1];
        int i, j;

        // Find m[i][j] for i = 0 (string is empty). It is only true for the leading part of p that looks like x*y*z*w*...
        m[0][0] = true;
        for (j = 2; j <= p.length(); j += 2) {
            if (p.charAt(j-1) != '*') {
                break;
            }
            m[0][j] = true;
        }
        
        // Find m[i][j] for j = 0 or 1.
        // When j == 0 (pattern is empty), only m[0][0] is true. We already dealt with this.
        // When j == 1 (pattern is a single char), only m[1][1] is possibly true, depending on whether s[0] matches p[0];
        if (s.length() > 0 && p.length() > 0) {
            m[1][1] = isCharMatch(s.charAt(0), p.charAt(0));
        }

        // Find m[i][j] for i >= 1 and j >= 2.
        for (i = 1; i <= s.length(); i++) {
            for (j = 2; j <= p.length(); j++) {
                // Does s[0..i-1] match p[0..j-1]?
                if (p.charAt(j-1) == '*') {
                    // p[0..j-1] ends with x*. We distinguish two cases:
                    // 1. x* matches nothing. We simply remove x*.
                    m[i][j] = m[i][j-2];
                    // 2. x* matches something, in this case, s[i-1] must match x,
                    //    we remove the matching char and keep the pattern as is.
                    if (isCharMatch(s.charAt(i-1), p.charAt(j-2))) {
                        m[i][j] = m[i][j] || m[i-1][j];
                    }
                } else {
                    m[i][j] = m[i-1][j-1] && isCharMatch(s.charAt(i-1), p.charAt(j-1));
                }
            }
        }
        
        return m[s.length()][p.length()];
    }

    private boolean isCharMatch(char s, char p) {
        return p == s || p == '.';
    }
}