描述
问题描述：在计算机中，通配符一种特殊语法，广泛应用于文件搜索、数据库、正则表达式等领域。现要求各位实现字符串通配符的算法。
要求：
实现如下2个通配符：
*：匹配0个或以上的字符（注：能被*和?匹配的字符仅由英文字母和数字0到9组成，下同）?：匹配1个字符
注意：匹配时不区分大小写。
输入：
通配符表达式；
一组字符串。
输出：
返回不区分大小写的匹配结果，匹配成功输出true，匹配失败输出false
数据范围：字符串长度 1≤s≤100
输入描述：
先输入一个带有通配符的字符串，再输入一个需要匹配的字符串
输出描述：
返回不区分大小写的匹配结果，匹配成功输出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 正则表达式API来做的话，有点不讲武德，毕竟这个题目就是要实现正则表达式功能。于是采用递归方法，也还是比较好理解。
- 因为匹配时不区分大小写，所以输入字符串先统一转为小写。
- 同时遍历通配符表达式和字符串，如果当前通配符是?，则跳过该位置不做判断，比较下一个字符。
- 如果是当前通配符是
*，则可以匹配任意多个字符，包括0个，此时可以有三种选择：- 1.匹配0个，通配符向后移动一个字符，字符串不动；
- 2.匹配1个，通配符和字符串都向后移动一个字符；
- 3.匹配多个，通配符不动，字符串向后移动一个字符。
- 还有一个注意点是匹配的字符仅由英文字母和数字0到9组成
/**
* Welcome to https://waylau.com
*/
package com.waylau.nowcoder.exam.oj.huawei;
import java.util.Scanner;
/**
* HJ71 字符串通配符。
* 描述：在计算机中，通配符一种特殊语法，广泛应用于文件搜索、数据库、正则表达式等领域。
* 现要求各位实现字符串通配符的算法。
* 要求：
* 实现如下2个通配符：
* *：匹配0个或以上的字符（注：能被*和?匹配的字符仅由英文字母和数字0到9组成，下同）
* ？：匹配1个字符
* 注意：匹配时不区分大小写。
* 输入：
* 通配符表达式；
* 一组字符串。
* 输出：
* 返回不区分大小写的匹配结果，匹配成功输出true，匹配失败输出false
* 数据范围：字符串长度：1≤s≤100
* 输入描述：
* 先输入一个带有通配符的字符串，再输入一个需要匹配的字符串
* 输出描述：
* 返回不区分大小写的匹配结果，匹配成功输出true，匹配失败输出false
* 示例1
* 输入：
* te?t*.*
* txt12.xls
*
* 输出：
* false
* @since 1.0.0 2022年8月28日
* @author <a href="https://waylau.com">Way Lau</a>
*/
public class HJ071StringWildcard {
public static void main(String[] args) {
// 输入
Scanner in = new Scanner(System.in);
// 先统一为小写
String wildcard = in.nextLine().toLowerCase();
String str = in.nextLine().toLowerCase();
// 输出
System.out.println(isMatch(wildcard, str, 0, 0));
// 关闭
in.close();
}
private static boolean isMatch(String wildcard,
String str, int wildcardP, int strP) {
// 两个字符串同时结束,返回true
if ((wildcard.length() == wildcardP)
&& (str.length() == strP)) {
return true;
} else if ((wildcard.length() == wildcardP)
|| (str.length() == strP)) {
// 两个字符串中有一个先结束，返回false
return false;
}
if ((wildcard.length() != wildcardP)
&& (str.length() == strP)) {
// wildcardArray里全是* 匹配结果为 True
// wildcardArray里不全是* 匹配结果为 False
for (int i = 0; i < wildcard.length(); i++) {
if (wildcard.charAt(i) != '*') {
return false;
}
}
return true;
}
char currentWildcard = wildcard.charAt(wildcardP);
char currentStr = str.charAt(strP);
// 匹配的字符仅由英文字母和数字0到9组成
if (currentWildcard != currentStr && !(Character
.isDigit(currentStr)
|| Character.isLetter(currentStr))) {
return false;
} else if (currentWildcard != currentStr
&& (Character.isDigit(currentStr)
|| Character
.isLetter(currentStr))) {
if (currentWildcard == '?') {
// 跳过，直接看下一位
isMatch(wildcard, str, wildcardP + 1,
strP + 1);
} else if (currentWildcard == '*') {
// 有三种选择：
// 1、匹配0个，通配符向后移动一个字符，字符串不动；
// 2、匹配1个，通配符和字符串都向后移动一个字符；
// 3、匹配多个，通配符不动，字符串向后移动一个字符。
return isMatch(wildcard, str, wildcardP + 1,
strP)
|| isMatch(wildcard, str,
wildcardP + 1, strP + 1)
|| isMatch(wildcard, str, wildcardP,
strP + 1);
} else {
return false;
}
} else if (currentWildcard == currentStr) {
isMatch(wildcard, str, wildcardP + 1, strP + 1);
}
return false;
}
}
但是这个递归在极端情况下，比如*大于8个，性能其极差。测试用例跑不过。比如下面的例子，花费几十分钟。
用例输入 h*h*ah**ha*h**h***hha hhhhhhhahhaahhahhhhaaahhahhahaaahhahahhhahhhahaaahaah 预期输出 false
我们注意到，用例中有可能会出现连续的*，此时，可以见多个连续*合并为一个*，减少递归的次数。
整个后代码如下：
/**
* Welcome to https://waylau.com
*/
package com.waylau.nowcoder.exam.oj.huawei;
import java.util.Scanner;
/**
* HJ71 字符串通配符。
* 描述：在计算机中，通配符一种特殊语法，广泛应用于文件搜索、数据库、正则表达式等领域。
* 现要求各位实现字符串通配符的算法。
* 要求：
* 实现如下2个通配符：
* *：匹配0个或以上的字符（注：能被*和?匹配的字符仅由英文字母和数字0到9组成，下同）
* ？：匹配1个字符
* 注意：匹配时不区分大小写。
* 输入：
* 通配符表达式；
* 一组字符串。
* 输出：
* 返回不区分大小写的匹配结果，匹配成功输出true，匹配失败输出false
* 数据范围：字符串长度：1≤s≤100
* 输入描述：
* 先输入一个带有通配符的字符串，再输入一个需要匹配的字符串
* 输出描述：
* 返回不区分大小写的匹配结果，匹配成功输出true，匹配失败输出false
* 示例1
* 输入：
* te?t*.*
* txt12.xls
*
* 输出：
* false
* @since 1.0.0 2022年8月28日
* @author <a href="https://waylau.com">Way Lau</a>
*/
public class HJ071StringWildcard {
public static void main(String[] args) {
// 输入
Scanner in = new Scanner(System.in);
// 先统一为小写
String wildcard = in.nextLine().toLowerCase();
String str = in.nextLine().toLowerCase();
// 缩减*号
wildcard = shortAsterisk(wildcard);
// 输出
System.out.println(isMatch(wildcard, str, 0, 0));
// 关闭
in.close();
}
private static boolean isMatch(String wildcard,
String str, int wildcardP, int strP) {
// 两个字符串同时结束,返回true
if ((wildcard.length() == wildcardP)
&& (str.length() == strP)) {
return true;
} else if ((wildcard.length() == wildcardP)
|| (str.length() == strP)) {
// 两个字符串中有一个先结束，返回false
return false;
}
if ((wildcard.length() != wildcardP)
&& (str.length() == strP)) {
// wildcardArray里全是* 匹配结果为 True
// wildcardArray里不全是* 匹配结果为 False
for (int i = 0; i < wildcard.length(); i++) {
if (wildcard.charAt(i) != '*') {
return false;
}
}
return true;
}
char currentWildcard = wildcard.charAt(wildcardP);
char currentStr = str.charAt(strP);
// 匹配的字符仅由英文字母和数字0到9组成
if (currentWildcard != currentStr && !(Character
.isDigit(currentStr)
|| Character.isLetter(currentStr))) {
return false;
} else if (currentWildcard != currentStr
&& (Character.isDigit(currentStr)
|| Character
.isLetter(currentStr))) {
if (currentWildcard == '?') {
// 跳过，直接看下一位
isMatch(wildcard, str, wildcardP + 1,
strP + 1);
} else if (currentWildcard == '*') {
// 有三种选择：
// 1、匹配0个，通配符向后移动一个字符，字符串不动；
// 2、匹配1个，通配符和字符串都向后移动一个字符；
// 3、匹配多个，通配符不动，字符串向后移动一个字符。
return isMatch(wildcard, str, wildcardP + 1,
strP)
|| isMatch(wildcard, str,
wildcardP + 1, strP + 1)
|| isMatch(wildcard, str, wildcardP,
strP + 1);
} else {
return false;
}
}
return isMatch(wildcard, str, wildcardP + 1, strP + 1);
}
// 缩减*号
private static String shortAsterisk(String str) {
char[] arr = str.toCharArray();
int len = arr.length;
// 只有1个元素直接返回了
if (len<=1) {
return str;
}
StringBuilder sb = new StringBuilder();
sb.append(arr[0]);
for (int i = 1; i< arr.length; i++) {
// 如果前面的也是*，说明有连续*，丢掉本次的*
if (arr[i] == '*' && arr[i-1] == '*') {
// do nothing
} else {
sb.append(arr[i]);
}
}
return sb.toString();
}
}
参考引用
- 本系列归档至https://github.com/waylau/nowcoder-exam-oj
- 《Java 数据结构及算法实战》：https://github.com/waylau/java-data-structures-and-algorithms-in-action
- 《数据结构和算法基础（Java 语言实现）》（柳伟卫著，北京大学出版社出版）：https://item.jd.com/13014179.html
京公网安备 11010502036488号