RegularExpresionMatching.java

public boolean isMatch(String s, String p) {
        if (s == null || p == null) {
            return false;
        }

        int row = s.length();
        int col = p.length();

        boolean[][] lookup = new boolean[row + 1][col + 1];

        lookup[0][0] = true;

        // init the init values
        for (int j = 1; j <= col; j++) {
            if (p.charAt(j - 1) == '*') {
                if (lookup[0][j - 1]) {
                    lookup[0][j] = true;
                } else if (j >= 2 && lookup[0][j - 2]) {
                    lookup[0][j] = true;
                }
            }
        }

        for (int i = 1; i <= row; i++) {
            for (int j = 1; j <= col; j++) {
                if (p.charAt(j - 1) == '*') {
                    // in the graph above referred as first if
                    if (lookup[i][j - 1]) {
                        lookup[i][j] = true;
                    }
                    // in the graph above referred as second if    
                    if (!lookup[i][j] && lookup[i - 1][j]) {
                        lookup[i][j] = (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.');
                    }
                    // in the graph above referred as third if
                    if (!lookup[i][j] && j >= 2 && lookup[i][j - 2]) {
                        lookup[i][j] = true;
                    }
                } else {
                    if (lookup[i - 1][j - 1] && ((p.charAt(j - 1) == s.charAt(i - 1)) || p.charAt(j - 1) == '.')) {
                        lookup[i][j] = true;
                    }
                }
            }
        }

        // Utilities.printBooleanMatrix(lookup);
        return lookup[row][col];
    }