6. Regular Expression Matching-正则表达式匹配

题目描述：

给定一个字符串 (s) 和一个字符模式 (p)。实现支持 ‘.’ 和 ‘‘ 的正则表达式匹配。
‘.’ 匹配任意单个字符。
‘‘ 匹配零个或多个前面的元素。
匹配应该覆盖整个字符串 (s) ，而不是部分字符串。
说明:
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。

输入输出Demo：

解析：在LeetCode上本题属于Hard题。典型的动态规划类型题目，动态规划类型题目非常重要。
对于一个位于字符模式p中的字符c来说，只有三种情况：

     1. c == '.'
     1. c == '*'
     1. c 为其他普通字符

我们先来看第一种情况，当c == ‘.’的时候，因为可以匹配任意字符，那么，直接跳过即可，对于第三种情况，那么只要s中对应的字符与字符c相同即可。接下来，再来看看最后一种情况。
如果c == ，那么代表可以匹配零个或者多个前面的字符，比如a可以匹配a、aaaa、aaaaa也可以匹配空字符，所以它其实是个修饰符，用来修饰它前面的字符，必须要跟其他字符一起使用，所以我们在一个个遍历模式串中的字符的时候，还需看看后面跟的字符是不是*，如果是的话，那么就要进行特殊处理了。

每次从p中拿出一个字符来与s中的字符进行匹配，如果该字符后续的字符不是，那么直接与s中对应字符进行匹配判断即可，如果匹配上了，那么就将两个游标都往后移动一位。如果匹配过程中遇到不相等的情况，则直接返回false。如果后续字符是，那么就如上面所分析的，分成两种情况，一种是匹配0个，那么只需要跳过p中的这两个字符，继续与s中的字符进行比较即可，如果是匹配多个，那么将s中的游标往后移动一个，继续进行判断，这两个条件只要其中一个能满足即可。




代码中是递归解法，去掉dp注释就是dp，效率提高很多

 class Solution {
        // 状态空间
        //Boolean[][] dp;

        public boolean isMatch(String text, String pattern) {
            //dp = new Boolean[text.length() + 1][pattern.length() + 1];
            return match(0, 0, text, pattern);
        }

        public boolean match(int i, int j, String text, String pattern) {
//            if (dp[i][j] != null) {
//                return dp[i][j];
//            }
            boolean ans;
            //递归出口
            if (j == pattern.length()) { //j到了模式串末尾
                ans = i == text.length();  //判断i是否也到了末尾，如果i到了末尾，就说明都匹配完了，返回true
            } else {
                //如果j没到模式串末尾
                /**
                 * 对于一个位于字符模式p中的字符c来说，只有三种情况：
                 *  c == '.'
                 *  c == '*'
                 *  c 为其他普通字符
                 */
                //第一种情况，当c == '.'的时候，因为可以匹配任意字符，那么，直接跳过即可
                //对于第三种情况，那么只要s中对应的字符与字符c相同即可
                boolean curMatch = (i < text.length() &&
                        (pattern.charAt(j) == text.charAt(i) ||
                                pattern.charAt(j) == '.'));

                //第二种情况分析
                /**
                 * 如果后续字符是*，那么就分成两种情况:
                 *      一种是匹配0个，那么只需要跳过p中的这两个字符，继续与s中的字符进行比较即可，
                 *      如果是匹配多个，那么将s中的游标往后移动一个，继续进行判断，
                 * 这两个条件只要其中一个能满足即可。
                 */
                if (j + 1 < pattern.length() && pattern.charAt(j + 1) == '*') {  //后续字符是*
                    ans = (match(i, j + 2, text, pattern) ||  //匹配0个
                            curMatch && match(i + 1, j, text, pattern));  //匹配多个（前提是当前字符匹配成功，也就是curMatch为true才生效）
                } else {
                    ans = curMatch && match(i + 1, j + 1, text, pattern); //如果后面字符不是*，那么就继续往后匹配
                }
            }
            //dp[i][j] = ans;
            return ans;
        }
    }