原文链接：https://leetcode-cn.com/problems/regular-expression-matching/solution/zheng-ze-biao-da-shi-pi-pei-by-leetcode/

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

方法 1：回溯
想法

如果没有星号（正则表达式中的 * ），问题会很简单——我们只需要从左到右检查匹配串 s 是否能匹配模式串 p 的每一个字符。

当模式串中有星号时，我们需要检查匹配串 s 中的不同后缀，以判断它们是否能匹配模式串剩余的部分。一个直观的解法就是用回溯的方法来体现这种关系。

public boolean isMatch(String s, String p) {
      // 如果匹配的规则串为空
        if (p.isEmpty()){
            // 直接返回
            return s.isEmpty();
        }
        
        // 第一个字符的匹配结果，每次递归都需要用到
        boolean first_match = ( !s.isEmpty() && ( p.charAt(0) == s.charAt(0) || p.charAt(0) == '.' ) );

        // 如果匹配串的长度大于2跟第一个字符是*
        if (p.length()>=2 && p.charAt(1)=='*'){
            // *不匹配任何字符，表示0
            return (isMatch(s,p.substring(2))
                    // *匹配一个字符，递归字符串
                    || (first_match && isMatch(s.substring(1),p))
            );
        }else {
            // 如果不是*
            return first_match && isMatch(s.substring(1),p.substring(1));
        }
    }