HJ71 题解 | #字符串通配符#

本来想暴力递归，但发现最后一组竟然超时了，同时发现“*”的通配条件复杂，由此推断递归造成的超时跟过多的“*”有关。

故本题思路：

1. 先分别统计通配符“?”和“*”的个数，这里先粗略认为“*”的个数>=8就过多。
2. 将所有情况分为3组：(1) “*” < 8; (2) “*” >= 8且“?” == 0; (3) “*” >= 8且“?” != 0。详情见代码注释。

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            String str1 = in.next();
            String str2 = in.next();
            str1 = str1.toLowerCase();
            str2 = str2.toLowerCase();
            System.out.println(match(str1, str2, 0, 0));
        }
    }
    
    public static boolean match(String str1, String str2, int p1, int p2){
        int n = 0, m = 0;
        for(int i = 0; i < str1.length(); i++){
            if(str1.charAt(i) == '?'){
                n++;
            }
            if(str1.charAt(i) == '*'){
                m++;
            }
        }
        
        //“*”较少，使用暴力递归
        if(m < 8){
        
            //递归结束的条件
            if(p1 == str1.length() && p2 == str2.length()){
                return true;
            }
            else if(p1 == str1.length() || p2 == str2.length()){
                return false;
            }
            else if(!Character.isLetter(str2.charAt(p2)) && !Character.isDigit(str2.charAt(p2)) && str1.charAt(p1) != str2.charAt(p2)){
                return false;
            }
            
            //如果本位是“?”，则两个字符串str1和str2均跳过本位比较下一位
            else if(str1.charAt(p1) == '?'){
                return match(str1, str2, p1+1, p2+1);
            }
            
            //如果本位是“*”，则考虑“*”代表0位，或代表1位，或代表多位。
            else if(str1.charAt(p1) == '*'){
                return match(str1, str2, p1+1, p2) || match(str1, str2, p1+1, p2+1) || match(str1, str2, p1, p2+1);
            }
            
            //如果本位是字母或数字且两个字符串的本位相等，则共同比较下一位
            else if(str1.charAt(p1) == str2.charAt(p2)){
                return match(str1, str2, p1+1, p2+1);
            }
            return false;
        }
        
        //“*”较多，则不使用递归
        
        //“*”较多，且无“?”。先判断开头结尾是不是字母或数字，如果是，则先比较两字符串的开头或结尾，不相同就直接结束程序，减少复杂度
        else if(m >= 8 && n == 0){
        
        　　//开头是字母或数字
            if(!str1.startsWith("*")){
                String str3 = "";
                int i = 0;
                while(str1.charAt(i) != '*'){
                    str3 += str1.charAt(i);
                    i++;
                }
                for(int a = 0; a < str3.length(); a++){
                    if(str3.charAt(a) != str2.charAt(a)){
                        return false;
                    }
                }
            }
            
            //结尾是字母或数字
            if(!str1.endsWith("*")){
                String str4 = "";
                int j = str1.length() - 1;
                while(str1.charAt(j) != '*'){
                    str4 += str1.charAt(j);
                    j--;
                }
                int pp1 = 0, pp2 = str2.length() - 1;
                while(pp1 < str4.length() && pp2 >= 0){
                    if(str4.charAt(pp1) != str2.charAt(pp2)){
                        return false;
                    }
                    pp1++;
                    pp2--;
                }
            }
            
            //开头与结尾都是“*”或开头与结尾的字符串均相等，则将str1以“*”分开，进一步判断分割形成的字串是否在str2中
            
            //将str1所有一个以上连续的“*”变成只有一个，便于分割
            char[] c1 = str1.toCharArray();
            for(int a = 0; a < c1.length; a++){
                if(c1[a] == '*' || c1[a] == '\0'){
                    if(c1[a+1] == '*'){
                        c1[a+1] = '\0';
                    }
                }
            }
            str1 = String.valueOf(c1);
            
            //对于每一个str1分割出来的字串，在str2中寻找第一次出现的位置，记为index，然后下一次搜寻范围从这个字串后边开始，即startIndex = index + sub.length()
            int startIndex = 0;
            for(String sub: str1.split("\\*")){
                int index = str2.indexOf(sub, startIndex);
                if(index == -1){              //代表str2中没有找到对应子串，即str1与str2不能匹配，返回false退出程序
                    return false;
                }
                else{
                    startIndex = index + sub.length();
                }
            }
        }
        
        //“*”较多，且有“?”
        else if(m >= 8 && n != 0){
            return false;                       //懒了没写，实际上前面已经可以通过所有的测试样例了，有大佬想出来了的话可以帮忙写一下
        }
        
    return false;
    }
}