首页 > 试题广场 >

字符串通配符

[编程题]字符串通配符

热度指数：180681 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

$\hspace{15pt}$ 在计算机中，通配符是一种特殊语法，广泛应用于文件搜索、数据库、正则表达式等领域。让我们来学习通配符的匹配规则：
$\hspace{23pt}\bullet\,$ $\texttt{`*'}$ 符号代表匹配 $0$ 个或以上的数字或字母；
$\hspace{23pt}\bullet\,$ $\texttt{`?'}$ 符号代表匹配 $1$ 个数字或字母；
$\hspace{23pt}\bullet\,$ 小写字母字符代表匹配自身和自身的大写字母形态；
$\hspace{23pt}\bullet\,$ 大写字母字符代表匹配自身和自身的小写字母形态；
$\hspace{23pt}\bullet\,$ 其他字符代表匹配自身。

$\hspace{15pt}$ 现在，对于给定的通配符字符串 $s$ 和目标字符串 $p$ ，不考虑大小写，请判断 $s$ 是否可以匹配得到 $p$ 。如果可以，输出 $\rm true$ ；否则，输出 $\rm false$ 。

$\hspace{15pt}$ 在本题中，给定的字符串由 ASCII 码在 $33$ 到 $126$ 范围内的可见字符构成。您可以参阅下表获得其详细信息（您可能关注的内容是，这其中不包含空格、换行）。 ../图片/AllAscii.png

输入描述:

第一行输入一个长度为 、由可见字符构成的通配符字符串 。
第二行输入一个长度为  、由可见字符构成的目标字符串 。

输出描述:

如果可以匹配得到，输出 ；否则，输出 。

示例1

输入

z
zz

输出

false

示例2

输入

Z*
zz

输出

true

说明

在这个样例中， 匹配 。注意，由于不区分大小写， 可以匹配 。

示例3

输入

?*
zz

输出

true

说明

在这个样例中， 匹配 、 匹配 。

示例4

输入

**Z
0QZz

输出

true

说明

在这个样例中，其中一种匹配方法是：
第一个  匹配 ；
第二个  匹配 ；
第三个  匹配 。

示例5

输入

??**
zz

输出

true

说明

 可以匹配  个字符。

示例6

输入

HH?*
HH##1

输出

false

说明

可被  和  匹配的字符不包含 。

算法知识视频讲解

Java

小煎饺子

屎山代码，也算做出来了，记录一下

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        boolean flag = false;
        Scanner in = new Scanner(System.in);
        String s1 = in.nextLine().toLowerCase();
        String s2 = in.nextLine().toLowerCase();
        flag=isSame(s1,s2);
        System.out.println(flag);
    }
    public static boolean isSame(String s1, String s2) {
        int i = 0, j = 0, index = 0;
        for (; i < s1.length() && j < s2.length(); j++) {
            if (s1.charAt(i) == '?') {         //第1种情况字符为‘？’
                if (Character.isLetter(s2.charAt(j)) || Character.isDigit(s2.charAt(j))) {
                    i++;
                } else {
                    break;
                }
            } else if (s1.charAt(i) == '*' && (i+1) < s1.length()) {   //第2种情况字符为‘*’，且不在字符串末尾
                i++;
                while(i < s1.length()&&(s1.charAt(i) == '*'||s1.charAt(i) == '?')){
                    i++;
                }
                if(i==s1.length()){
                    return true;
                }
                while (j<s2.length()&&s1.charAt(i) != s2.charAt(j)) {
                    if(!Character.isLetter(s2.charAt(j)) &&!Character.isDigit(s2.charAt(j))){
                        if(s1.charAt(i) != s2.charAt(j)){
                            return false;
                        }
                    }
                    j++;
                }
                if (j == s2.length()) {
                    break;
                }
                index = j;
                if(isSame(s1.substring(i, s1.length()), s2.substring(j, s2.length()))){
                    return true;
                }
                while (j<s2.length()&&!isSame(s1.substring(i, s1.length()), s2.substring(j, s2.length()))) {
                    j=index+1;
                    while (j<s2.length()&&s1.charAt(i) != s2.charAt(j)) {
                    j++;
                    }
                    if (j == s2.length()) {
                        break;
                    }
                     if(isSame(s1.substring(i, s1.length()), s2.substring(j, s2.length()))){
                    return true;
                    }
                    index = j;
                }
            } else if (s1.charAt(i) == '*' && (i + 1) == s1.length()) {  //第2种情况字符为‘*’，在字符串末尾
                return true;
            } else {                                  //第3种情况字符为普通字符
                if (s1.charAt(i) == s2.charAt(j)) {
                    i++;
                } else {
                    break;
                }
            }
        }
        if(i==s1.length()&&j==s2.length()){
            return true;
        }else if(j==s2.length()&&s1.substring(i,s1.length()).split("[*?]").length==0){
            return true;
        }else{
            return false;
        }
    }
}

发表于 2025-04-14 21:33:53 回复(0)

Java

Sen🍓🍀

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.next().toUpperCase(); // 都转大写
        String p = in.next().toUpperCase(); // 都转大写

        // // 去除s中连续*，防止超时
        // String ss = "";
        // int i = 0;
        // while (i < s.length()) {
        //     if (s.charAt(i) != '*') {
        //         ss += s.charAt(i);
        //         i++;
        //     } else {
        //         ss += '*';
        //         while (i < s.length() && s.charAt(i) == '*') {
        //             i++;
        //         }
        //     }
        // }

        // // 构造正则
        // String regex = "";
        // for (char c : ss.toCharArray()) {
        //     if (c == '*') {
        //         regex += "[0-9A-Z]*";  // * ：0个或以上的数字或字母；
        //     } else if (c == '?') {
        //         regex += "[0-9A-Z]";   // ? ：1个数字或字母
        //     } else {
        //         regex += c;          // 其他： 由于都转大写，匹配自身
        //     }
        // }

        String regex = s.replaceAll("[*]+", "[0-9A-Z]*").replaceAll("[?]", "[0-9A-Z]"); // 看了别人的，直接replace
        System.out.print(p.matches(regex));
    }
}

// 不去重，就会超时的用例
// h*h*ah**ha*h**h***hha
// hhhhhhhahhaahhahhhhaaahhahhahaaahhahahhhahhhahaaahaahs

发表于 2025-01-28 17:34:09 回复(0)

Java

代码边界

动态规划

import java.util.*;

public class Main{

public static void main(String []args){

Scanner in = new Scanner(System.in);

while(in.hasNext()){

String key = in.nextLine().toLowerCase(Locale.ROOT);

String line = in.nextLine().toLowerCase(Locale.ROOT);

boolean[] dp = new boolean[line.length() + 1];

dp[0] = true;

for (char k : key.toCharArray()) {

boolean pre = dp[0];

dp[0] = dp[0] && '*' == k;

for (int i = 1; i < dp.length; i++) {

char c = line.charAt(i - 1);

boolean temp = dp[i];

if (!Character.isLetter(c) && !Character.isDigit(c)) {

if (k != '*') {

dp[i] = c == k && pre;

}

}else if (k == '?') {

dp[i] = pre;

}else if (k == '*') {

dp[i] |= dp[i - 1];

}else {

dp[i] = c == k && pre;

}

pre = temp;

}

System.out.println(dp[dp.length - 1]);

}

in.close();

}

发表于 2024-07-07 15:38:02 回复(1)

Java

香辣素毛肚

import java.util.Scanner;
import java.util.regex.Pattern;

public class Main {
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        String pattern=in.nextLine().toLowerCase();
        String s=in.nextLine().toLowerCase();
        pattern=pattern.replaceAll("\\*+","*");
        pattern=pattern.replace(".", "\\.");
        pattern=pattern.replace("?", "([a-z]|[0-9])+");
        pattern=pattern.replace("*", "([a-z]|[0-9])*");
        //System.out.println(pattern);
        System.out.println(Pattern.matches(pattern,s));   ;

    }
}

有一种简单粗暴的美

编辑于 2024-03-27 14:46:56 回复(0)

Java

Kili_66

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String reg = in.nextLine().toLowerCase();
        String str = in.nextLine().toLowerCase();
        reg = reg.replaceAll("\\*+","[a-z0-9]*").replaceAll("\\?","[a-z0-9]");
        System.out.println(str.matches(reg));
    }
}

发表于 2023-11-27 16:31:50 回复(0)

Java

调皮的外卷侠说又不是不能用

// 用正则替换
public static boolean resolve(String s, String content) {
    s = s.toLowerCase();
    content = content.toLowerCase();
    // 多个*相当于一个*
    s = s.replaceAll("\\*+", "*");
    // *?*或*?或?*相当于匹配至少一个字符
    s = s.replaceAll("\\*\\?\\*|\\*\\?|\\?\\*", "[0-9a-z]+");
    s = s.replaceAll("\\*", "[0-9a-z]*");
    s = s.replaceAll("\\?", "[0-9a-z]{1}");
    s = "^" + s + "$";
    return content.matches(s);
}

发表于 2023-07-26 15:56:17 回复(0)

Java

metazz

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

String regxExpress = "[0-9A-Za-z]";

while (scanner.hasNextLine()) {

String regx = scanner.nextLine().toLowerCase();

String str = scanner.nextLine().toLowerCase();

char[] regxs = regx.toCharArray();

char[] strs = str.toCharArray();

int rp = 0;

int sp = 0;

Boolean flag = true;

while (rp < regxs.length && sp < strs.length) {

if (regxs[rp] == '?') {

if (!String.valueOf(strs[sp]).matches(regxExpress)) {

System.out.println("false");

return;

}

if (flag) {

rp++;

sp++;

flag = true;

} else {

rp++;

if (rp == regxs.length) {

System.out.println("true");

return;

}

} else if (regxs[rp] == '*') {

rp++;

flag = false;

} else {

if (flag) {

if (regxs[rp] != strs[sp]) {

System.out.println("false");

return;

} else {

rp++;

sp++;

flag = true;

}

} else {

while (sp < strs.length) {

if (regxs[rp] == strs[sp]) {

if (sp < strs.length - 1 && strs[sp] == strs[sp + 1]) {

sp++;

} else {

sp++;

rp++;

flag = true;

break;

}

} else {

if (!String.valueOf(strs[sp]).matches(regxExpress)) {

System.out.println("false");

return;

}

sp++;

}

if ((regxs[regxs.length - 1] != '*' && rp < regxs.length) ||

(sp < strs.length && regxs[regxs.length - 1] != '*' )) {

System.out.println("false");

return;

}

System.out.println("true");

return;

}

发表于 2023-07-19 23:08:51 回复(0)

Java

大凡牛牛牛

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            String tpstr = sc.nextLine().toLowerCase();//通配符
            String needstr = sc.nextLine().toLowerCase();//需要被匹配的
            System.out.println(isMatch(tpstr,needstr));
        }
    }

    public static boolean isMatch(String s, String p) {
        //只向右向下向右下
        boolean[][] dp=new boolean[s.length()+1][p.length()+1];
        dp[0][0]=true;
        //第一行为'*'则一行都为true；
        for(int i=1;i<=p.length();i++){
                if(s.charAt(0)=='*'){
                    dp[1][i]=true;
                } 
            }
        for(int i=1;i<=s.length();i++){
            for(int j=1;j<=p.length();j++){
                if(s.charAt(i-1)==p.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1]||dp[i-1][j];
                }
                if(s.charAt(i-1)=='?'&&((p.charAt(j-1)>='a'&&p.charAt(j-1)<='z')||(p.charAt(j-1)>='0'&&p.charAt(j-1)<='9'))){
                    dp[i][j]=dp[i-1][j-1];
                }
                if(s.charAt(i-1)=='*'&&((p.charAt(j-1)>='a'&&p.charAt(j-1)<='z')||(p.charAt(j-1)>='0'&&p.charAt(j-1)<='9'))){
                    dp[i][j]=dp[i-1][j]||dp[i][j-1]||dp[i-1][j-1];
                }
            }
        }
        return dp[s.length()][p.length()];
    }

}

发表于 2023-07-19 14:13:14 回复(0)

Java

夏小楠

import java.util.*;
//用正则表达式打败模糊匹配！
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String matchRule = in.next().toLowerCase(Locale.ROOT);//将字符串中的大写字母转小写
        String scStr = in.next().toLowerCase(Locale.ROOT);
        matchRule = matchRule.replaceAll("\\*+", "[a-z0-9]*");//替换1个或多个*
        matchRule = matchRule.replaceAll("\\?", "[a-z0-9]");//替换问号
        System.out.print(scStr.matches(matchRule));
    }
}

发表于 2023-04-12 15:50:22 回复(1)

Java

晴婉刘

// 和普通的区别是， * 和 ？ 只能表数字和字母（所以要加上额外判断）
// 注意： * 表 0 个时不需要是数字或者字母
import java.lang.String;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String pattern;
        while ((pattern = br.readLine()) != null) {
            pattern = toLowerStr(pattern.trim());
            String str = toLowerStr(br.readLine().trim());
            System.out.println(isMatch(str, pattern));
        }
    }

    public static String toLowerStr(String str) {
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < str.length(); i++) {
            if (Character.isUpperCase(str.charAt(i))) {
                sb.append(Character.toLowerCase(str.charAt(i)));
            } else {
                sb.append(str.charAt(i));
            }
        }
        return sb.toString();
    }

    public static boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int i = 1; i <= n; ++i) {
            if (p.charAt(i - 1) == '*') {
                dp[0][i] = true;
            } else {
                break;
            }
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (s.charAt(i - 1) == p.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    boolean isLetterOrDigit = Character.isLetter(s.charAt(i - 1)) ||
                                              Character.isDigit(s.charAt(i - 1));
                    if (p.charAt(j - 1) == '*') {
                        // 表 0 个时不需要是数字或者字母
                        dp[i][j] = (dp[i - 1][j] && isLetterOrDigit) || dp[i][j - 1];
                    } else if (p.charAt(j - 1) == '?' && isLetterOrDigit) {
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                }
            }
        }
        return dp[m][n];
    }


}

发表于 2023-04-06 11:10:41 回复(1)

Java

梁sirkevin

我这个很ok
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String a = "";
        String b = "";
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            a = in.nextLine().toLowerCase(Locale.ROOT);
            b = in.nextLine().toLowerCase(Locale.ROOT);
        }
        //多个星号换成一个星号
        String regex = a.replaceAll("\\*{2,}","\\*");
        // //？换成一个0-9a-z正则
        regex = regex.replace("?", "[0-9a-z]{1}");
        //*换成n个0-9a-z正则
        regex = regex.replace("*", "[0-9a-z]{0,}");
        boolean isMatch = b.matches(regex);
        System.out.println(isMatch);
    }
}

发表于 2022-12-27 16:08:26 回复(0)

Java

Sawyer_lILi

import java.util.*;

import java.io.*;

// 三种方法，递归、正则表达、动态规划，

//注意到我简化了第一个字符串，因为*和多个*作用相同，简化后很多超时用例就能跑通了

public class Main {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

String value;

while (sc.hasNextLine()) {

value = sc.nextLine();

String target = sc.nextLine();

value = value.toLowerCase();

target = target.toLowerCase();

// System.out.println(matchStr(value,target));

//简化一下，*和********其实没区别，但是在计算中容易超时间、空间

String simpled_value = value.replaceAll("\\*{2,}","\\*");

// System.out.println(compareChar(simpled_value,target,0,0));

System.out.println(isMatch(simpled_value,target));

}

public static boolean compareChar(String s1,String s2,int p1,int p2){

if(p1 == s1.length() && p2 ==s2.length()){

return true; //在上一次递归中，p1、p2分别指向s1、s2的末尾，

//并且p1指向一个‘？’或‘*’，或者p1p2

//所指向的字符相同，p1p2分别加1，才有可能结果为true，而只要有一个true

//之前所有的递归结果都是true

}

else if(p1 == s1.length() || p2 == s2.length()){

return false;//else p1、p2并不是在上一次的递归中都是指向末尾，

//而是只有一个指向了末尾，那么

//这样的递归结果就是false，因为之后缺失了，

//长短不一样,不用比较也知道不匹配了。

}

//假如读取到了*，说明可能匹配0到无穷多个字符，那么就有两种处理方式，一种是继续匹配s2的下一个字符,可以理解为*匹配了无穷多个字符；

//一种是s1、s2都进一步匹配，可以理解为*匹配了一个字符

if(s1.charAt(p1)=='*'){

if(p1==s1.length()-1&&p2==s2.length()-1){

return compareChar(s1,s2,p1+1,p2+1);

}

return compareChar(s1,s2,p1,p2+1) || compareChar(s1,s2,p1+1,p2);

}

//假如读取到了？，说明只能匹配一个字符，那就只能都继续进一步匹配了，因为不存在匹配多位的情况

else if(s1.charAt(p1)=='?'){

if(Character.isLetterOrDigit(s2.charAt(p2))){

return compareChar(s1,s2,p1+1,p2+1);

}

//?无法匹配非数字字母字符，故return false

else{

return false;

}

//不是通配符，那么就是字符，数字字符特殊符号都有可能，但是相同，那么就跳过

else if(s1.charAt(p1)==s2.charAt(p2)){

return compareChar(s1,s2,p1+1,p2+1);

}

//不相同，那么匹配失败

else {

return false;

}

//本题实际就是异化的正则化，将*？的功能用正则化实现即可

public static boolean matchStr(String s1,String s2){

String regx = s1.replaceAll("\\*{2,}","\\*");

regx = regx.replaceAll("\\?","[0-9a-z]{1}");

regx = regx.replaceAll("\\*","[0-9a-z]{0,}");

return s2.matches(regx);

}

//动态规划核心要点：画一个表格，第一行第一列是边界条件，需要在正式计算前填好，

//例如本题中的第一个for循环

//这个二维的数组（表格），每个格子(i,j)中的boolean值表示第一个字符串从0到i，与第二个字符串从

//0到j的子串的匹配情况(true&nbs***bsp;false)，boolean 默认false，然后通过子字符串与当前字符串的关联

//依次将其余格子填好，最终结果是格子最右下角的那个值

public static boolean isMatch(String s1,String s2){

char[] chars1 = s1.toCharArray();

char[] chars2 = s2.toCharArray();

boolean[][] dp = new boolean[chars1.length+1][chars2.length+1];

dp[0][0] = true; //两个子字符串都是空显然是匹配的，0=0

//因为*可以匹配0个字符，所以第一个字符串是以*或者多个连续的*开头，那么他们都是true

for(int i=1;i<chars1.length+1;i++){

if(chars1[i-1]=='*'){

dp[i][0]=true;

}else break;

}

for(int i=1;i<=chars1.length;i++){

for(int j=1;j<=chars2.length;j++){

if(chars1[i-1]==chars2[j-1]){

dp[i][j]=dp[i-1][j-1]; //假如字符相同，可以“消去”这个字符串，然后再比较

//消去之后的匹配结果

}

if(chars1[i-1]=='?'&&Character.isLetterOrDigit(chars2[j-1])){

dp[i][j]=dp[i-1][j-1]; //假如是?且要匹配的是字母或数字(因为无法匹配其他字符)

//同样可以视为"消去"之后比较匹配结果

}

else if(chars1[i-1]=='*'&&Character.isLetterOrDigit(chars2[j-1])){

//第一个理解为*匹配0个字符，相当于没有

//第二个理解为匹配多个字符

//最后一个好理解，*本来就有？的功能

dp[i][j]=dp[i-1][j]|dp[i][j-1]|dp[i-1][j-1];

}

return dp[chars1.length][chars2.length];

}

发表于 2022-12-02 00:22:07 回复(0)

Java

无穷大的分母

import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            String regex = in.next().toLowerCase();
            String target = in.next().toLowerCase();
            
            boolean dp[][]=new boolean[target.length() + 1][regex.length() + 1];
            dp[0][0]=true;
            for(int i = 1; i <= target.length(); i++){
                if (regex.charAt(i - 1) == '*') {
                dp[0][i] = true;
                } else {
                    break;
                }
            }

            for(int i = 1; i <= target.length(); i++){
                for(int j = 1 ; j <= regex.length(); j++){
                    if (target.charAt(i - 1) == regex.charAt(j - 1)) {
                        dp[i][j]=dp[i-1][j-1];
                    } else if (Character.isDigit(target.charAt(i - 1)) || Character.isLetter(target.charAt(i - 1))) {
                        if (regex.charAt(j - 1) == '*') {
                            dp[i][j] = dp[i - 1][j - 1] || dp[i - 1][j] || dp[i][j - 1];
                        } else if (regex.charAt(j - 1) == '?') {
                            dp[i][j] = dp[i - 1][j - 1];
                        }
                    }
                }
            }
            System.out.println(dp[target.length()][regex.length()]);
        }
    }
}

发表于 2022-10-21 15:20:32 回复(1)

Java

牛客151616704号

贴个 dp 版的正确答案吧，思路都在注释里。牛客的样例数据太弱了，很多人根本没注意到通配符匹配的条件，依然阴差阳错的 ac 了。

import java.util.*;

public class Main {
    // 状态定义：f(i, j): s2 的前 i 个字符能否匹配 s1 的前 j 个字符
    // 状态转移方程：
    // (1) 如果 s1 的第 j 个字符是 '?'，说明 s1 的第 j 个字符可以和 s2 的第 i 个字符匹配
    //     看 s1 的前 j - 1 个能否与 s2 的前 i - 1 个匹配，即 f(i, j) = f(i - 1, j - 1)
    // (2) 如果 s1 的第 j 个字符是非通配符，则看 s1 的第 j 个字符能否和 s2 的第 i 个字符匹配
    //     如果能，就是 f(i, j) = f(i - 1, j - 1)；如果不能，f(i, j) = false
    // (3) 如果 s1 的第 j 个字符是 '*'，则有三种可能：
    //     ① '*' 匹配 0 个 s2[i]，即 f[i][j] = f[i][j - 1]
    //     ② '*' 匹配 1 个 s2[i]，即 f[i][j] = f[i - 1][j - 1]
    //     ③ '*' 匹配多个 s2[i]，即 f[i][j] = f[i - 1][j]
    // 初始化：dp[0][0]代表两个空串匹配。dp[i][0]是 s2 和空串匹配，永远为 false
    //        dp[0][j]是 s1 和空串匹配，当 s1 只有 *，则和空串匹配为 true，出现一个非 *，则匹配为 false
    public static boolean process(String s1, String s2) {
        int n1 = s1.length(); // 通配符串
        int n2 = s2.length(); // 匹配串
        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();
        // 二维表中，横的是通配符串，纵的是匹配串
        boolean[][] dp = new boolean[n2 + 1][n1 + 1];
        // 初始化
        dp[0][0] = true;
        for(int i = 1; i <= n2; i++) { // c2 和空串匹配，永远为 false
            dp[i][0] = false;
        }
        boolean flg = false;
        for(int j = 1; j <= n1; j++) {
            // c1 只有 *，则和空串匹配为 true，出现一个非 *，则匹配为 false
            if(!flg && c1[j - 1] == '*') {
                dp[0][j] = true;
            } else {
                flg = true;
                dp[0][j] = false;
            }
        }
        
        for(int i = 1; i <= n2; i++) {
            for(int j = 1; j <= n1; j++) {
                if(c1[j - 1] == '*') {
                    // 只有英文字母和数字能被通配符匹配
                    if((c2[i - 1] >= '0' && c2[i - 1] <= '9') || (c2[i - 1] >= 'a' && c2[i - 1] <= 'z')
                    || (c2[i - 1] >= 'A' && c2[i - 1] <= 'Z')) {
                        dp[i][j] = dp[i - 1][j] || dp[i][j - 1] || dp[i - 1][j - 1];
                    } else { // 不匹配，为 false
                        dp[i][j] = false;
                    }
                } else { // ? 和普通字符
                    if(match(c1[j - 1], c2[i - 1])) {
                        dp[i][j] = dp[i - 1][j - 1];
                    } else {
                        dp[i][j] = false;
                    }
                }
            }
        }
        return dp[n2][n1];
    }

    public static boolean match(char c1, char c2) {
        if(c1 == '?') return true;
        // 小写字母全部转为大写字母再比较
        if(c1 >= 'a' && c1 <= 'z') {
            c1 = (char)(c1 - 'a' + 'A');
        }
        if(c2 >= 'a' && c2 <= 'z') {
            c2 = (char)(c2 - 'a' + 'A');
        }
        return c1 == c2;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s1 = sc.next();
        String s2 = sc.next();
        System.out.println(process(s1, s2));
    }
}

发表于 2022-10-14 21:00:48 回复(0)

Java

努力学习ing！！

动态规划，改了又改，可算全过了

记录一下：1、这里不区分大小写，所以用char == 的话需要提前把两个串全转大写或者小写

2、？ * 只能匹配字母或者数字，此时需要判断s中的字符是不是复合

3、遇到*号和 s中不是字母和数字的情况，不能一棍子打死，如果上面是true，也就是*此时代表空串，也是true，而从左边过来（即，匹配了1+个字符了，遇到非字母数字就是false了）

import java.io.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String p;
        while ((p = br.readLine()) != null) {
            String s = br.readLine();
            System.out.println(isMatch(p, s));
        }
    }
    public static boolean isMatch(String p, String s) {
        int m = p.length() + 1;
        int n = s.length() + 1;
        s = s.toLowerCase();
        p = p.toLowerCase();

        boolean[][] dp = new boolean[m][n];
        dp[0][0] = true;
        if (p.charAt(0) == '*') {
            for (int i = 0; i < n; i++) {
                dp[1][i] = true;
            }
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (p.charAt(i - 1) == s.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (p.charAt(i - 1) == '*' || p.charAt(i - 1) == '?') {
                    char c = s.charAt(j - 1);
                    boolean b = (c >= 48 && c <= 57) || (c >= 97 && c <= 122);
                    if (p.charAt(i - 1) == '*') {
                        dp[i][j] = dp[i - 1][j] || (dp[i][j - 1] && b);
                    } else if (p.charAt(i - 1) == '?' && b) {
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                }

            }
        }
        // for (boolean[] t : dp) {
        //     System.out.println(Arrays.toString(t));
        // }
        return dp[m - 1][n - 1];
    }
}

发表于 2022-10-01 15:21:50 回复(0)

Java

Cyan_Mu

import java.util.Scanner;


public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        String regex=sc.nextLine();
        String str=sc.nextLine();
        System.out.println(match(regex,str));
    }
    public static boolean match(String regex,String str){
        int m=str.length();
        int n =regex.length();
        char[] strs=str.toCharArray();
        char[] regexs=regex.toCharArray();
        boolean[][] dp=new boolean[n+1][m+1];
        dp[0][0]=true;
        for (int i=0;i<m;i++){
            if(Character.isLetter(strs[i])) strs[i]=Character.toLowerCase(strs[i]);
        }
        for(int i=1;i<=n;i++){
            if(regexs[i-1]=='*')dp[i][0]=dp[i-1][0];
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(!isWord(strs[j-1])){
//                    如果是特殊字符，必须这个值相等才能匹配上，否则直接为false
                    if(regexs[i-1]==strs[j-1])dp[i][j]=dp[i-1][j-1];
                    continue;
                };
                char c=strs[j-1];
//                如果不是特殊字符，是*的情况则只要dp[i-1][j]||dp[i-1][j-1]||dp[i][j-1]=true都能匹配上
                if(regexs[i-1]=='*')dp[i][j]=dp[i-1][j]||dp[i-1][j-1]||dp[i][j-1];
//                如果不是特殊字符，是？或相等的情况只要dp[i-1][j-1]=true就能匹配上
                else if(regexs[i-1]=='?'||Character.toLowerCase(regexs[i-1])==c)dp[i][j]=dp[i-1][j-1];

            }
        }

发表于 2022-08-18 21:55:17 回复(0)

Java

牛客408432666号

原来题目无视大小写，害的我一直不知道为什么看这个测试用例像是错的。。。

发表于 2022-08-05 15:27:39 回复(0)

Java

YZC_LinHina

import java.io.IOException;
import java.util.Scanner;

public class Main {
//https://www.nowcoder.com/practice/43072d50a6eb44d2a6c816a283b02036?tpId=37&tqId=21294&rp=1&ru=/exam/oj/ta&qru=/exam/oj/ta&sourceUrl=%2Fexam%2Foj%2Fta%3Fdifficulty%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tpId%3D37%26type%3D37&difficulty=3&judgeStatus=undefined&tags=&title=
    public static void main(String[] args) throws IOException {
        Scanner scan = new Scanner(System.in);
        String regex = scan.nextLine();
        String s = scan.nextLine();
        regex = regex.toLowerCase();
        s = s.toLowerCase();
        int i1 = 0, i2= 0;
        int m = s.length();
        int n = regex.length();
        boolean[][] dp = new boolean[m+1][n+1];
        dp[0][0] = true;
        for (int i = 1; i <= n; i++) {
            if(regex.charAt(i-1)=='*'){
                dp[0][i] = true;
            }else{
                break;
            }
        }
        for (int i = 1; i <=m ; i++) {
            for (int j = 1; j <=n ; j++) {
                //字符合法
                if(legal(s.charAt(i-1))){
                    //当表达式为‘*’时，可以匹配多个字符
                    if(regex.charAt(j-1)=='*'){
                        //由上一个字符是否匹配这个位置（匹配字符数>1）以及前一个匹配符是否和当前字符匹配(匹配字符数=0)共同决定
                        dp[i][j] = dp[i][j-1]||dp[i-1][j];
                    }else if(regex.charAt(j-1)=='?'||s.charAt(i-1)==regex.charAt(j-1)){
                        //如果是相等或者是==？的情况，则交给字符以及匹配符各自的前一位决定
                        dp[i][j] = dp[i-1][j-1];
                    }
                }else{
                    //字符不合法
                    //相等则当前匹配，情况交给字符以及匹配符各自的前一位决定
                    if(s.charAt(i-1)==regex.charAt(j-1)){
                        dp[i][j] = dp[i-1][j-1];
                        //不相等则看前面的匹配符有没有匹配到过的dp[i][j-1]
                    }else{
                        dp[i][j] = dp[i][j-1];
                    }
                }
            }
        }
        System.out.println(dp[m][n]);

    }
    //判断字符是否为合法字符
    public static boolean legal(char c){
        return c>='0'&&c<='9'||c>='a'&&c<='z';
    }
}

******** 44 hard难度的题目变形，这里放个中等😭

编辑于 2022-07-28 16:29:19 回复(0)

提交观点

问题信息

字符串

难度：

51条回答 2959收藏 36081浏览

通过挑战的用户

查看代码

猪儿拱

2023-02-26 22:43:42
帅阿衰

2023-01-08 10:20:13
hnSS

2023-01-02 16:02:27
芊樱烛渊

2022-10-30 20:15:16
牛客39961...

2022-10-30 10:33:48

字符串通配符

输入描述:

输出描述:

输入

输出

输入

输出

说明

输入

输出

说明

输入

输出

说明

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题