当前位置：首页 > news >正文

牛客出bug（华为机试HJ71）

news 2025/8/6 7:47:34

Hj71：字符串通配符

描述

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

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

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

输出：

返回不区分大小写的匹配结果，匹配成功输出true，匹配失败输出false

数据范围：字符串长度 1≤s≤100

进阶：时间复杂度：O(n2) ，空间复杂度 O(n)

输入描述：

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

输出描述：

返回不区分大小写的匹配结果，匹配成功输出true，匹配失败输出false

上述为题目，都提示时间复杂度为 O(n2) 了，基本都能想到动态规划吧，废话不多说，先上代码

public static void main(String[] args) {Scanner in = new Scanner(System.in);String match = in.nextLine();String target = in.nextLine();System.out.println(dp(match, target) ? "true" : "false");}/*** pass:32/34* eg:* a*?*c* a@c* 预计：false！！！！！！！！！！！！！！！todo sotmw???????* 实际：true* @param match* @param target* @return*/public static boolean dp(String match, String target) {int m = match.length();int n = target.length();boolean[][] dp = new boolean[m][n];// 初始化dpfor (int j = 0; j < n; ++j) {char c = match.charAt(0);if (c == '*') {dp[0][j] = true;//通配符匹配多个if (m > 1) {dp[1][j] = match.charAt(1) == target.charAt(j);//第一位的 * 可能不匹配，多初始化一行}}if (j == 0 && (c == '?' || c == target.charAt(0))) {//dp[0][0] 必须初始化dp[0][j] = true;}}// 常规dpfor (int i = 0; i < m - 1; ++i) {for (int j = 0; j < n - 1; ++j) {if (dp[i][j]) {char mat = match.charAt(i + 1);if (mat == '*') {for (int j0 = j; j0 < n; ++j0) {dp[i + 1][j0] = true;}} else if (mat == '?') {dp[i + 1][j + 1] = true;} else {dp[i + 1][j + 1] = mat == target.charAt(j + 1);}}}}return dp[m - 1][n - 1];}