ac

对于字符串str，其中绝对不含有字符’.’和‘*’。再给定字符串exp，其中可以含有’.’或’‘*’，’*’字符不能是exp的首字符，并且任意两个’*‘字符不相邻。exp中的’.’代表任何一个字符，exp中的’*’表示’*‘的前一个字符可以有0个或者多个。请写一个函数，判断str是否能被exp匹配(注意：输入的数据不保证合法，但只含小写字母和‘.’和‘*’)。

时间复杂度O(n^2*m),额外空间复杂度O(n^2),(n为字符串str长度，m为字符串exp长度)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static long mod = (long)Math.pow(2,29);

    public static void main(String[] args) throws Exception {
        String str = reader.readLine();
        String exp = reader.readLine();
        String ans = match(str, exp) ? "YES" : "NO";
        System.out.println(ans);
    }

    // * 前一个可以0个或多个, * 确定不是p的首字符
    // . 任意一个
    public static  boolean match(String s, String p)
    {
        int sLen = s.length();
        int pLen = p.length();
        // 特殊情况处理
        if(sLen == 0 && pLen == 0){
            return true;
        }
        if(sLen != 0 && pLen == 0){
            return false;
        }
        if(sLen == 0 && pLen != 0){
            if(pLen > 1 && p.charAt(1) == '*'){
                return match(s, p.substring(2));
            }else {
                return false;
            }
        }
        // p[0] 为 . 的情况
        if(p.charAt(0) == '.'){
            if(pLen > 1 && p.charAt(1) == '*'){
                // * 匹配 0 次 或 多次
                return match(s, p.substring(2)) ||
                        match(s.substring(1), p) ||
                        match(s.substring(1), p.substring(2));
            }else {
                return match(s.substring(1), p.substring(1));
            }
        }else {
            if(s.charAt(0) == p.charAt(0)){
                if(pLen > 1 &&  p.charAt(1) == '*'){
                    return  match(s.substring(1), p) ||
                            match(s, p.substring(2)) ||
                            match(s.substring(1), p.substring(2));
                }
                return match(s.substring(1), p.substring(1));
            }else {
                if(pLen > 1 &&  p.charAt(1) == '*'){
                    return match(s, p.substring(2));
                }
            }
        }
        return false;
    }
}
/*
abc
abc

YES

abcd
.*

YES
*/