首页 > 试题广场 >

字符串通配符

[编程题]字符串通配符
  • 热度指数：174112 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

问题描述：在计算机中，通配符一种特殊语法，广泛应用于文件搜索、数据库、正则表达式等领域。现要求各位实现字符串通配符的算法。
要求：
实现如下2个通配符：
*：匹配0个或以上的字符（注：能被*和?匹配的字符仅由英文字母和数字0到9组成，下同）
？：匹配1个字符

注意：匹配时不区分大小写。

输入：
通配符表达式；
一组字符串。

输出：

返回不区分大小写的匹配结果，匹配成功输出true，匹配失败输出false
数据范围：字符串长度：
进阶：时间复杂度：，空间复杂度：

输入描述:
先输入一个带有通配符的字符串，再输入一个需要匹配的字符串


输出描述:
返回不区分大小写的匹配结果，匹配成功输出true，匹配失败输出false
示例1

输入

te?t*.*
txt12.xls

输出

false
示例2

输入

z
zz

输出

false
示例3

输入

pq
pppq

输出

false
示例4

输入

**Z
0QZz

输出

true
示例5

输入

?*Bc*?
abcd

输出

true
示例6

输入

h*?*a
h#a

输出

false

说明

根据题目描述可知能被*和?匹配的字符仅由英文字母和数字0到9组成，所以?不能匹配#，故输出false
示例7

输入

p*p*qp**pq*p**p***ppq
pppppppqppqqppqppppqqqppqppqpqqqppqpqpppqpppqpqqqpqqp

输出

false
算法知识视频讲解
添加回答
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头像 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头像 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头像 梁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头像 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号头像 牛客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！！头像 努力学习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头像 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号头像 牛客408432666号
原来题目无视大小写，害的我一直不知道为什么看这个测试用例像是错的。。。
发表于 2022-08-05 15:27:39 回复(0)
Java
YZC_LinHina头像 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)
Java
lie_pig头像 lie_pig
我这份代码全通过了，但是输入h*a    h####a返回值是true，按照题意应该是false，但是样例全通过了 
import java.util.*; public class Main { public static void main(String[] args) { Scanner input = new Scanner(System.in); while (input.hasNext()) { String pattern = input.nextLine().toLowerCase(); String str = input.nextLine().toLowerCase(); String[] split = str.split(" "); List<Boolean> result = new ArrayList<>(); for (int i = 0; i < split.length; i++) { result.add(isMatch(pattern,split[i]));
            } for (int i = 0; i < result.size(); i++) { if(i==0){ System.out.println(result.get(i));
                }else { System.out.println(","+result.get(i));
                }
            }
        }
    } public static boolean isMatch(String pattern,String str){ int s = str.length(); int p = pattern.length(); boolean[][] dp = new boolean[s + 1][p + 1]; dp[0][0] = true; for (int i = 1; i <= p; ++i) { if (pattern.charAt(i-1)=='*'){ dp[0][i] = true;
            }else { break;
            }
        } for (int i = 1; i <= s; ++i) { for (int j = 1; j <= p; ++j) { if(pattern.charAt(j-1)=='*'){ dp[i][j] = dp[i][j-1]||dp[i-1][j];
                }else if ((pattern.charAt(j-1)=='?'&&digitAndLetter(str.charAt(i-1)))||str.charAt(i-1)==pattern.charAt(j-1)){ dp[i][j] = dp[i-1][j-1];
                }
            }
        } return dp[s][p];
    } public static boolean digitAndLetter(char c){ return Character.isDigit(c)||Character.isLetter(c);
    }
}




发表于 2022-07-02 23:18:18 回复(0)
提交观点

问题信息

字符串
难度：
49条回答 35054浏览

热门推荐

通过挑战的用户

查看代码

相关试题

字符串通配符

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号