剑指offer：正则表达式匹配

题意描述

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

解题思路

一、思路一

1. 两个字符串都为空，返回true
2. 当第一个字符串不空，而第二个字符串空了，返回false（因为这样，就无法匹配成功了,而如果第一个字符串空了，第二个字符串非空，还是可能匹配成功的，比如第二个字符串是“aaaa”,由于‘ * ’之前的元素可以出现0次，所以有可能匹配成功）
3. 开始匹配第一个字符，这里有两种可能：匹配成功或匹配失败。但考虑到pattern下一个字符可能是‘ * ’， 这里我们分两种情况讨论：pattern下一个字符为‘ * ’或不为‘ * ’：
   • pattern下一个字符不为‘ * ’：
     • 如果str第一个字符和ptr中的第一个字符相匹配，那么str和ptr都后移一个字符，然后匹配剩余的。
     • 如果str第一个字符和ptr中的第一个字符相不匹配，直接返回false。
   • pattern下一个字符为‘ * ’时，稍微复杂一些，因为‘ * ’可以代表0个或多个。这里把这些情况都考虑到：
     • x* 匹配0个字符，str不变，ptr后移两位，跳过这个’ * ‘
     • x* 匹配1个字符时，str+1，ptr+2，匹配str下个字符，并且跳过’ * ‘
     • x* 匹配多个字符时，str+1，ptr不变，继续匹配str下个字符
     • 匹配一个也可以看成匹配多个

    public class Solution {
        public boolean match(char[] str, char[] pattern){
            if(str == null && pattern == null) return true;	//str、pattern都为空，返回true
            if(str != null && pattern == null) return false;//str不为空，pattern为空，匹配失败
            return matchCore(str,0,pattern,0);
        }
        public boolean matchCore(char[] str, int s1, char[] ptr, int p1) {
            //str匹配到尾部，ptr匹配到尾部，匹配成功
            if(s1 == str.length && p1 == ptr.length){
                return true;
            }
            //str没有匹配到尾部，ptr匹配到尾部，匹配失败
            if(s1 != str.length && p1 == ptr.length){
                return false;
            }
            //p1的下一个字符为‘*’，并且没有越界
            if(p1+1

    public class Solution {
        public boolean match(char[] str, char[] pattern){
            if(str == null || pattern == null) return true;
            boolean[][] dp = new boolean[str.length+1][pattern.length+1];
            dp[str.length][pattern.length] = true; //末尾“”与“”一定匹配
            for(int i=str.length;i>=0;i--){	//从空串开始匹配
                for(int j=pattern.length-1;j>=0;j--){//从最后一个字符开始匹配
                    if(j+1