首页 > 试题广场 >

字符串通配符

[编程题]字符串通配符

热度指数：186215 时间限制：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

牛客298721346号

可以从动态规划的角度考虑。

不妨以示例4(**Z,0QZZ)为例讨论。先考虑通配符串的第一位“*”：它可以匹配0QZZ的前0/1/2/3/4个字符（因为0QZZ里没有一般符号），于是(**Z,0QZZ)被分解成5个子问题：(*Z,0QZZ)，(*Z,QZZ)，(*Z,ZZ)，(*Z,Z)，(*Z,“”)，而每一个子问题同样可以通过此法分解……这样就可以构建动态规划用到的二维数组，而数组的两个坐标分别是当前通配符串和当前待测串的起始元素下标。（最后一行和最后一列分别代表“空通配符的匹配”以及“通配符对空串的匹配”，如果不这么写的话，初始化会稍微有些麻烦。）

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        String regex = in.nextLine().toLowerCase();
        String s = in.nextLine().toLowerCase();
        System.out.println(isMatched(regex, s));
    }


    private static boolean isMatched(String regex, String s) {
        int regexLength = regex.length();
        int sLength = s.length();
        boolean[][] result = new boolean[regexLength + 1][sLength + 1];

        for (int j = 0; j < sLength + 1; j++) {
            result[regexLength][j] = (j == sLength);
        }

        for (int i = regexLength - 1; i > -1; i--) {
            for (int j = 0; j < sLength; j++) {
                switch (regex.charAt(i)) {
                    case '*':
                        result[i][j] = result[i + 1][j]; //只有“*”才可以匹配空串
                        for (int k = j + 1; k < sLength + 1 ; k++) {
                            result[i][j] = result[i][j] || result[i + 1][k];
                            if (k < sLength && isCommonChar(s.charAt(k))) //“*”并不能匹配一般字符，所以不应该继续查找
                            break;
                        }
                        break;
                    case '?':
                        if (isCommonChar(s.charAt(j))) { //“?”必须匹配至少1个数字或字母
                            result[i][j]=false;
                            break;
                        }
                        for (int k = j + 1; k < sLength + 1 ; k++) {
                            result[i][j] = result[i][j] || result[i + 1][k];
                            if (k < sLength && isCommonChar(s.charAt(k))) //和上面类似的判断逻辑
                            break;
                        }
                        break;
                    default:
                        result[i][j] = regex.charAt(i) == s.charAt(j) && result[i + 1][j + 1]; //对于一般字符，不但要对应相等，还要保证在子问题上也匹配
                        break;
                }
            }
            result[i][sLength] = regex.charAt(i) == '*' && result[i + 1][sLength]; //检查此处的通配串是否可以匹配空串“”
        }
        return result[0][0];
    }

    private static boolean isCommonChar(char c) {
        return (c < 'a' || c > 'z') && (c < '0' || c > '9');
    }
}

发表于 2025-05-23 15:59:38 回复(0)

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)

提交观点

问题信息

字符串

难度：

52条回答 3109收藏 37626浏览

通过挑战的用户

查看代码

猪儿拱

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

字符串通配符

输入描述:

输出描述:

输入

输出

输入

输出

说明

输入

输出

说明

输入

输出

说明

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题