算法-19.正则表达式匹配

请实现一个函数用来匹配包含'. '和''的正则表达式。模式中的字符'.'表示任意一个字符，而''表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式，即每个字符都在另一个字符串中能找到对应的匹配字符。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但与"aa.a"和"ab*a"均不匹配。

一、递归算法

    /**
     * 正则表达式匹配
     * @param s
     * @param p
     * @return
     * 举例：比如s="aaa"，p="ab*ac*a"
     * 第一次调用isMatch的时候，第一个字符匹配，且p的第二个字符不是*，第二次是return true，所以本次也是return true
     * 第二次调用isMatch的时候，s="aa"，p="b*ac*a",第一个字符不匹配，且p的第二个字符是*，第三次return true，所以本次也是return true
     * 第三次调用isMatch的时候，isMatch(s, p.substring(2))，s="aa"，p="ac*a"
     * 此时第一个字符匹配，且p的第二个字符不是*，第四次是return true，所以本次也是return true
     * 第四次调用isMatch的时候，s="a"，p="c*a"，
     * 此时第一个字符不匹配，且p的第二个字符是*，因为第五次return true所以本次也是return true
     * 第五次调用isMatch的时候，isMatch(s, p.substring(2))，s="a"，p="a"
     * 都只有一个字符，且匹配，所以return true
     */
    public static boolean isMatch(String s, String p) {
        if (p.length() <=0) return s.length() <= 0;
        // 判断第一个字符是否匹配
        boolean match = (s.length() > 0 && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.'));
        // 如果第二个字符是*
        if (p.length() > 1 && p.charAt(1) == '*') {
            // isMatch(s, p.substring(2))如果第一个字符不匹配，那么验证从p的第三个字符开始的字符串与s是否匹配
            // 如果第一个字符匹配，那么从s的第二个字符开始判断与p是否匹配
            return isMatch(s, p.substring(2)) || (match && isMatch(s.substring(1), p));
        } else {
            // 如果第二个不是*，且第一个字符匹配，而分别从第二个字符开始继续匹配
            return match && isMatch(s.substring(1), p.substring(1));
        }
    }

二、动态规划

    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;
    }

这个算法比较难，转载自：
【LeetCode】正则表达式匹配（动态规划）