西安做网站公司报价,企业网站引导页模板,公司宣传册模板ppt,wordpress网页图标Hj71#xff1a;字符串通配符
描述
问题描述#xff1a;在计算机中#xff0c;通配符一种特殊语法#xff0c;广泛应用于文件搜索、数据库、正则表达式等领域。现要求各位实现字符串通配符的算法。 要求#xff1a; 实现如下2个通配符#xff1a; *#xff1a;匹配0个…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* ac* 预计falsetodo 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];} 这个用例用眼睛都能匹配它告诉我说不行就问有没有被坑的感觉
分割线
后来我看到了
*匹配0个或以上的字符注能被*和?匹配的字符仅由英文字母和数字0到9组成下同 人为埋雷被坑的感觉更强烈了
搞些杂七杂八的消耗别人的时间精力完全违背了练习算法的初衷伤心了
