請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)用來匹配包含'. '和''的正則表達(dá)式。模式中的字符'.'表示任意一個(gè)字符，而''表示它前面的字符可以出現(xiàn)任意次（含0次）。在本題中，匹配是指字符串的所有字符匹配整個(gè)模式，即每個(gè)字符都在另一個(gè)字符串中能找到對(duì)應(yīng)的匹配字符。例如，字符串"aaa"與模式"a.a"和"abaca"匹配，但與"aa.a"和"ab*a"均不匹配。

一、遞歸算法

    /**
     * 正則表達(dá)式匹配
     * @param s
     * @param p
     * @return
     * 舉例：比如s="aaa"，p="ab*ac*a"
     * 第一次調(diào)用isMatch的時(shí)候，第一個(gè)字符匹配，且p的第二個(gè)字符不是*，第二次是return true，所以本次也是return true
     * 第二次調(diào)用isMatch的時(shí)候，s="aa"，p="b*ac*a",第一個(gè)字符不匹配，且p的第二個(gè)字符是*，第三次return true，所以本次也是return true
     * 第三次調(diào)用isMatch的時(shí)候，isMatch(s, p.substring(2))，s="aa"，p="ac*a"
     * 此時(shí)第一個(gè)字符匹配，且p的第二個(gè)字符不是*，第四次是return true，所以本次也是return true
     * 第四次調(diào)用isMatch的時(shí)候，s="a"，p="c*a"，
     * 此時(shí)第一個(gè)字符不匹配，且p的第二個(gè)字符是*，因?yàn)榈谖宕蝦eturn true所以本次也是return true
     * 第五次調(diào)用isMatch的時(shí)候，isMatch(s, p.substring(2))，s="a"，p="a"
     * 都只有一個(gè)字符，且匹配，所以return true
     */
    public static boolean isMatch(String s, String p) {
        if (p.length() <=0) return s.length() <= 0;
        // 判斷第一個(gè)字符是否匹配
        boolean match = (s.length() > 0 && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.'));
        // 如果第二個(gè)字符是*
        if (p.length() > 1 && p.charAt(1) == '*') {
            // isMatch(s, p.substring(2))如果第一個(gè)字符不匹配，那么驗(yàn)證從p的第三個(gè)字符開始的字符串與s是否匹配
            // 如果第一個(gè)字符匹配，那么從s的第二個(gè)字符開始判斷與p是否匹配
            return isMatch(s, p.substring(2)) || (match && isMatch(s.substring(1), p));
        } else {
            // 如果第二個(gè)不是*，且第一個(gè)字符匹配，而分別從第二個(gè)字符開始繼續(xù)匹配
            return match && isMatch(s.substring(1), p.substring(1));
        }
    }

二、動(dòng)態(tài)規(guī)劃

    private static boolean[][] memo;

    public static boolean isMatch1(String s, String p) {
        memo = new boolean[s.length() + 1][p.length() + 1];
        return match(0, 0, s, p);
    }

    public static boolean match(int i, int j, String text, String pattern) {
        if (memo[i][j]) {
            return memo[i][j];
        }
        boolean ans;
        if (j == pattern.length()){
            ans = i == text.length();
        } else{
            boolean curMatch = (i < text.length() &&
                    (pattern.charAt(j) == text.charAt(i) ||
                            pattern.charAt(j) == '.'));

            if (j + 1 < pattern.length() && pattern.charAt(j+1) == '*'){
                ans = (match(i, j+2, text, pattern) ||
                        curMatch && match(i+1, j, text, pattern));
            } else {
                ans = curMatch && match(i+1, j+1, text, pattern);
            }
        }
        memo[i][j] = ans;
        return ans;
    }

這個(gè)算法比較難，轉(zhuǎn)載自：
【LeetCode】正則表達(dá)式匹配（動(dòng)態(tài)規(guī)劃）