java

题目描述：
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

实例1：
输入：s = “aa”, p = “a”
输出：false
解释：“a” 无法匹配 “aa” 整个字符串。

实例2：
输入：s = “aa”, p = “a*”
输出：true
解释：因为 ‘*’ 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 ‘a’。因此，字符串 “aa” 可被视为 ‘a’ 重复了一次。

示例 3：

输入：s = “ab”, p = “."
输出：true
解释：".” 表示可匹配零个或多个（‘*’）任意字符（‘.’）。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/regular-expression-matching
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

```java

```java
public class LeecodeTest {
    public boolean solve(String s, String p, int index1, int index2) {
//        递归终止条件
//        字符串s匹配结束（并且）{p匹配结束（或者）[p的最后一个字符（index2+1）是“*）]}如：s:abbbb;p:ab*（中间匹配过程更趋向于情况二中的第二个选择
//        该条件用来判断结尾处的情况
        if (index1 == s.length() && (index2 == p.length() || (index2 + 1 == p.length() - 1 && p.charAt(index2 + 1) == '*'))) {
            return true;
        }
//        第二个递归终止条件:两个字符串长度不同，较短的先匹配完了
        if (index1 == s.length() || p.length() == index2) {
//          字符串s先到末尾   s:abc  ; p:abcd*f*e*  匹配到c处字符串s后为空，再往后移,index2指向‘d’，则检查index2后面的字符是否可以变成空
            if (index1 == s.length()) {
                return change(p, index2);
            } else {
//                字符串p先匹配完了
                return false;
            }
        }
//     情况二：   此种情况为index2的下一个字符为”*“，所以分开讨论
        if (index2 + 1 < p.length() && p.charAt(index2 + 1) == '*') {
            if (judge(s.charAt(index1), p.charAt(index2))) {
// 两种选择：1.s:abbb q:ab*bbb(让q中的b出现0次）
// 2.s:abbba,q:ab*a(让q中的b出现一次或多次，即当前的index1已经匹配过了，所以向下执行index1+1，而q中的b是多次出现所以s中的字符以至于index2比较即可，直至不等
                return solve(s, p, index1, index2 + 2) || solve(s, p, index1 + 1, index2);
            } else {
//                该情况为：index1和index2中的字符未匹配且index2+1==“*”，所以index2+1无效直接从index2+2处开始匹配
                return solve(s, p, index1, index2 + 2);
            }
        }
//     情况一：   当前两个下标所指的字符匹配，且后面没有“*”
        if (judge(s.charAt(index1), p.charAt(index2))) {
            return solve(s, p, index1 + 1, index2 + 1);
        }
        return false;//当前index1所指字符与index2所指字符不一致
    }

    public boolean change(String p, int index2) {
        while (index2 < p.length()) {
            if (index2 + 1 < p.length() && p.charAt(index2 + 1) == '*') {
                index2 += 2;//加2可以直接跳过‘*’
            } else {
                return false;
            }
        }
        return true;
    }

    public boolean judge(char s, char p) {
        if (s == p || p == '.') {
            return true;
        }
        return false;
    }

该方法没有使用动态规划，而是递归解决
学习视频链接：https://www.bilibili.com/video/BV1z7411c7yG?spm_id_from=333.1007.top_right_bar_window_default_collection.content.click