题解 | #正则表达式匹配# 不同于精华题解的方法，递归

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str string字符串
     * @param pattern string字符串
     * @return bool布尔型
     */
    public boolean match(String str, String pattern) {
        // write code here
        char[] chs1 = str.toCharArray();
        char[] chs2 = pattern.toCharArray();
        boolean flag = fis(0, 0, chs1, chs2);
        return flag;
    }

    public boolean fis(int i, int j, char[] chs1, char[] chs2) {
        if (i == chs1.length && j == chs2.length) {
            return true;
        } else if (i == chs1.length || j == chs2.length) {
            return false;
        }
        char ch1 = chs1[i];
        char ch2 = chs2[j];
        //匹配带*
        if (j < chs2.length - 1 && chs2[j + 1] == '*') {
            j += 2;
            //一个都不匹配
            if (fis(i, j, chs1, chs2)) {
                return true;
            }
            i++;
            while (i <= chs1.length) {
                //匹配.*
                if (ch2 == '.') {
                    if (fis(i, j, chs1, chs2)) {
                        return true;
                    }
                    i++;
                //匹配n*a 和 a*
                } else if (chs1[i - 1] == ch2) {
                    if (fis(i, j, chs1, chs2)) {
                        return true;
                    }
                    i++;
                } else {
                    return false;
                }
            }
        //匹配.或者a=a
        } else if (ch2 == '.' || ch1 == ch2) {
            if (fis(i + 1, j + 1, chs1, chs2)) {
                return true;
            //防止最后带*
            } else if (j < chs2.length - 2 && chs2[j + 2] == '*') {
                j += 2;
                if (fis(i + 1, j + 1, chs1, chs2)) {
                    return true;
                }
            }
        } else {
            return false;
        }
        return false;
    }
}