题解 | #字符串通配符#

不知道为啥，第一种方法总能通过，第二种方法有时候能通过，而且时间比第一种更短，但有时候又只能通过33组案例，最后一组案例超时。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s1 = sc.nextLine().toLowerCase();
        String s2 = sc.nextLine().toLowerCase();
        System.out.println(matchStr1(s1, s2));
    }

    //递归1:从后往前
    public static boolean matchStr1(String s1, String s2) {
        if (s1.length() == 0 && s2.length() == 0 ) {
            return true;
        } else if (s1.length() == 0 && s2.length() != 0 ) {
            return false;
        }
        int i = s1.length() - 1, j = s2.length() - 1;
        if (s1.charAt(i) == '?') {
            if (j < 0 || (!Character.isLetter(s2.charAt(j)) &&
                          !Character.isDigit(s2.charAt(j)))) {
                return false;
            } else {
                return matchStr1(s1.substring(0, i), s2.substring(0, j));
            }
        } else if (s1.charAt(i) == '*') {
            if (j < 0 || (!Character.isLetter(s2.charAt(j)) &&
                          !Character.isDigit(s2.charAt(j)))) {
                return matchStr1(s1.substring(0, i), s2.substring(0, j + 1));
            } else {   //可能匹配0个，1个，多个
                return matchStr1(s1.substring(0, i), s2.substring(0, j + 1)) ||
                       matchStr1(s1.substring(0, i), s2.substring(0, j)) ||
                       matchStr1(s1.substring(0, i + 1), s2.substring(0, j));
            }
        } else {
            if (i >= 0 && j >= 0 && s1.charAt(i) == s2.charAt(j)) {
                return matchStr1(s1.substring(0, i), s2.substring(0, j));
            } else {
                return false;
            }
        }
    }

    //方法2(33/34组用例通过):您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。
    public static boolean matchStr2(String s1, String s2) {
        int i = 0, j = 0;
        for (; i < s1.length() && j < s2.length(); i++, j++) {
            if (s1.charAt(i) == '?') {
                if (!Character.isLetter(s2.charAt(j)) && !Character.isDigit(s2.charAt(j))) {
                    return false;
                }
            } else if (s1.charAt(i) == '*') {
                int end = j;
                while (end < s2.length() && (Character.isLetter(s2.charAt(end)) ||
                                             Character.isDigit(s2.charAt(end)))) {
                    end++;
                }
                for (int k = j; k <= end; k++) {
                    if (matchStr2(s1.substring(i + 1), s2.substring(k))) {
                        return true;
                    }
                }
                return false;
            } else {
                if (s1.charAt(i) != s2.charAt(j)) {
                    return false;
                }
            }
        }
        if (i == s1.length() && j == s2.length()) {
            return true;
        } else {
            return false;
        }
    }
}