Regular Expression Matching.java

public class Solution {
    public boolean isMatch(String s, String p) {
        if (s == null || p == null)
            return false;
        int len2 = s.length();
        int len1 = p.length();
        boolean[][] arr = new boolean[len1 + 1][len2 + 1];
        arr[0][0] = true;
        for (int i = 0; i < len1; i++) {
            if (p.charAt(i) != '*')
                arr[i + 1][0] = false;
            else
                arr[i + 1][0] = arr[i - 1][0];
        }
        for (int i = 0; i < len1; i++) {
            for (int j = 0; j < len2; j++) {
                if (p.charAt(i) == s.charAt(j) || p.charAt(i) == '.')
                    arr[i + 1][j + 1] = arr[i][j];
                else if (p.charAt(i) == '*') {
                    arr[i + 1][j + 1] = arr[i - 1][j + 1] || arr[i][j + 1] || (arr[i + 1][j] && (p.charAt(i - 1) == s.charAt(j) || p.charAt(i - 1) == '.'));
                } else
                    arr[i + 1][j + 1] = false;
            }
        }
        return arr[len1][len2];
    }
}