Given an input string (s) and a pattern (p), implement regular expression matching with support for'.'and'*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover theentireinput string (not partial).

Note:

• scould be empty and contains only lowercase lettersa-z.
• pcould be empty and contains only lowercase lettersa-z, and characters like .or *.

递归

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

        if(p.length() == 0)
            return s.length() == 0;

        if(p.length() == 1) {
            if(s.length() == 0 || s.length() > 1)
                return false;

            return s.charAt(0) == p.charAt(0) || p.charAt(0) == '.';
        }

        if(p.charAt(1) != '*') {
            if(s.length() == 0)
                return false;

            if(s.charAt(0) == p.charAt(0) || p.charAt(0) == '.')
                return isMatch(s.substring(1), p.substring(1));

            return false;
        } else {
            if(s.length() == 0)
                return isMatch(s, p.substring(2));

            if(isMatch(s, p.substring(2)))
                return true;

            int i = 0;
            while(i < p.length() && (p.charAt(i) == s.charAt(0) || p.charAt(i) == '.')) {
                if(isMatch(s.substring(1), p.substring(i)))
                    return true;
                i++;
            }

            return false;
        }

    }
}

DP，dp的顺序，或者说dp[i][j]应 该代表0-i, 0-j 还是 i-s.length(), j - p.length()可能有点想不清楚，但是回忆一下递归的方法就比较容易想到了，在判断前面两个字符的情况之后，结果取决于后面的子字符串是否匹配，所以应该倒过来遍历，dp[i][j] = f(dp[i + n][j + m]) (m, n > 0)

class Solution {
    public boolean isMatch(String s, String p) {
        boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
        dp[s.length()][p.length()] = true;

        for(int i = s.length(); i >= 0; i--) {
            for(int j = p.length() - 1; j >= 0; j--) { 
                boolean firstMatch = (i < s.length()) && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.');

                if(j + 1 < p.length() && p.charAt(j + 1) == '*') {
                    dp[i][j] = dp[i][j + 2] || (firstMatch && dp[i + 1][j]);
                } else {
                    dp[i][j] = firstMatch && dp[i + 1][j + 1];
                }
            }
        }

        return dp[0][0];
    }
}