每日一题-正则表达式匹配-0715

题目：

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘’ 的正则表达式匹配。
‘.’ 匹配任意单个字符
'’ 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

解题思路：

1. 通过递归的方式，从头开始走

2. 当p的下一个字符是*号的时候，就开始发挥作用了，这个时候就会有两种情况：
   第一种：当前两个字符串的字符是相等的，就可以走以下三种情况：（1）p字符串当前的字符是多余的，s不动，p往后面走两格；（2）都正常往后走一个格；（3）当前的p可能是少的，那就让当前的字符多用几次，j不动
   第二种：当前的字符不想等，p就只能向后走两个格，当前p的字符和后面的️都起不到作用了

3. 判断当前两个字符串的字符是否相等，相等的话，都继续往后走

4. 如果不相等，并且没有️可以利用的时候，那么p当中就有s字符串不存在的字符，即肯定不是完全包含的。

️：过程中有一些边界条件需要考虑，比如s已经走到了结束，但是p没有结束，就存在一种可能，p还剩下一个字符和一个️，可以当作0次处理，跳过当前的字符

代码：

class Solution {
    
    public boolean isMatch(String s, String p) {
    
        if(s == null || p == null)
            return false;
        return recur(s, 0, p, 0);
    }
    private boolean recur(String s, int i, String p, int j){
    
        //两个字符串都到达了末尾,p尽到了职责
        if(i == s.length() && j == p.length())
            return true;
        //p已经没有能用来匹配s的字符
        if(i != s.length() && j == p.length())
            return false;
        if((j + 1 < p.length() && p.charAt(j + 1) == '*')){
    
            if(i == s.length())
                return recur(s, i, p, j + 2);
            if((s.charAt(i) == p.charAt(j)) ||(s.charAt(i) != ' ' && p.charAt(j) == '.')){
    
                //当前的字符是相等的
                return recur(s, i+1, p, j + 2) || //️处理的就是前面的字符只出现一次
                recur(s, i+1, p, j) || //p的字符不够用，可以继续使用
                recur(s, i, p, j + 2); //p的字符多余，自己往后跳，s就当看不到哈哈哈
            }else{
    
                //当前的字符不相等，p只能跳过
                return recur(s, i, p, j + 2);
            }
        }
        if(i >= s.length())
            return false;
        if((s.charAt(i) == p.charAt(j)) ||(s.charAt(i) != ' ' && p.charAt(j) == '.'))
            return recur(s, i + 1, p, j + 1); 
        return false;
    }
}