力扣10. 正则表达式匹配

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

说明:

s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。

递归解法

/*
这个题一开始理解错题了，题的意思是：.代表一个任意字符，a*代表匹配任意多个字符a

如果s和p长度都为0，返回true
如果p长度为0，s长度不为0，返回false
如过s长度为0，那么只有p是a*b*c*才能匹配，返回true

如果s的最后一个字符等于p的最后一个字符或者p的最后一个字符。继续去匹配前面的字符

如果最后一个字符匹配不上，有两种情况
第一种：p最后一个字符不为*，则返回false
第二种：p为*
    第二种又要细分为一下情况
        1：p的倒数第二个字符与s的最后一个字符不匹配，去掉p的后面两个字符
        2：p的倒数第二个字符与s的最后一个字符匹配，这种情况直接去掉s的最后一个字符

*/
class Solution {
    public boolean isMatch(String s, String p) {
        int lens = s.length(),lenp = p.length();
        if(lens == 0 && lenp == 0) return true;

        if(lenp == 0 && lens != 0) return false;

        if(lens == 0){
            if((lenp & 1) == 1) return false;//p为奇数个肯定匹配不上
            for(int i = 1;i <= lenp;i+=2){
                if(p.charAt(i) != '*'){
                    return false;
                }
            }
            return true;
        }

        int i = lens - 1,j = lenp - 1;
        if(s.charAt(i) == p.charAt(j) || p.charAt(j) == '.'){
            return isMatch(s.substring(0,i),p.substring(0,j));
        }

        if(p.charAt(j) == '*'){
            if(p.charAt(j-1) != s.charAt(i)&&p.charAt(j-1) != '.'){
                return isMatch(s,p.substring(0,j-1));
            }else{
                return isMatch(s.substring(0,i),p) || isMatch(s,p.substring(0,j-1)) || isMatch(s.substring(0,i),p.substring(0,j-1));
            }
        }

        return false;
    }
}