010.md

10. Regular Expression Matching

Solution 1 (O(mn))

// Dynamic programming
class Solution {
    public boolean isMatch(String s, String p) {
        int length1 = s.length(), length2 = p.length();
        boolean ans[][] = new boolean[length1 + 1][length2 + 1];
        ans[0][0] = true;
        for (int i = 1; i <= length1; i++)
            ans[i][0] = false;
        for (int i = 2; i <= length2; i++)
            if (p.charAt(i - 1) == '*')
                ans[0][i] = ans[0][i - 2];
        for (int i = 1; i <= length1; i++) {
            for (int j = 1; j <= length2; j++) {
                if (p.charAt(j - 1) == '*') {
                    if (p.charAt(j - 2) == '.') {
                        ans[i][j] = ans[i][j - 2] | ans[i - 1][j];
                    } else {
                        if (s.charAt(i - 1) != p.charAt(j - 2)) {
                            ans[i][j] = ans[i][j - 2];
                        } else {
                            ans[i][j] = ans[i][j - 2] | ans[i - 1][j];
                        }
                    }
                } else if (p.charAt(j - 1) == '.') {
                    ans[i][j] = ans[i - 1][j - 1];
                } else {
                    ans[i][j] = ans[i - 1][j - 1] &
                        (s.charAt(i - 1) == p.charAt(j - 1));
                }
            }
        }
        return ans[length1][length2];    
    }
}