RegexMatchDP.java

public class RegexMatchDP {
    public static void test() {
        RegexMatchDP sut = new RegexMatchDP();
        String[][] samples = new String[][]{
                {"abcdefg", "a*b*c*de.*"},
                {"abcdefg", ".*"},
                {"abcdefg", "ad.*"}, // no match
                {"abcdf", "a*b*c*de.*"}, // no match
                {"airbnb", "a*.*b*"},
        };
        for (String[] sample : samples) {
            System.out.println("Text: " + sample[0] + " "
                    + (sut.isMatch(sample[0], sample[1]) ? "Matches:" : "Doesn't Match:")
                    + " '" + sample[1] + "'"
            );
        }
    }

    public boolean isMatch(String s, String p) {
        boolean[][] T = new boolean[s.length() + 1][p.length() + 1];
        T[0][0] = true;
        // i is the iterator for (Rows => String)
        // j is the iterator for (Columns => Pattern)
        // We just populate the first row cause it would help us later (but No need to do that for first column)
        for (int i = 1; i < T[0].length; i++) if (p.charAt(i - 1) == '*') T[0][i] = T[0][i - 2];
        for (int i = 1; i < T.length; i++) {
            for (int j = 1; j < T[0].length; j++) {
                if (p.charAt(j - 1) == s.charAt(i - 1) || p.charAt(j - 1) == '.') {
                    T[i][j] = T[i - 1][j - 1];
                } else if (p.charAt(j - 1) == '*') {
                    T[i][j] = T[i][j - 2];
                    if (p.charAt(j - 2) == '.' || p.charAt(j - 2) == s.charAt(i - 1)) {
                        T[i][j] = T[i][j] || T[i - 1][j];
                    }
                } else {
                    T[i][j] = false;
                }
            }
        }
        return T[s.length()][p.length()];
    }
}