代码实现类似通配符的匹配

59 阅读 0 评论 39 点赞

我是靠谱客的博主可耐鲜花，最近开发中收集的这篇文章主要介绍代码实现类似通配符的匹配，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

/**如题：
*类似通配符的匹配
* 说明：实现支持 '.' 和 '*' 的类似通配符的匹配，规则如下：
* 1. '.' 匹配任意单个字符
* 2. '*' 匹配零个或多个前面的元素
* 3. isMatch(s, r); s 是匹配的目标字符串，r 是带匹配符的字符串
* 4. r 的匹配应该覆盖 s
*
* 示例：
* isMatch('aa','a') // return false
* isMatch('aa','aa') // return true
* isMatch('aaa','aa') // return false
* isMatch('aa', 'a*') // return true
* isMatch('aab', 'a*') // return false
* isMatch('aa', '.*') // return true
* isMatch('ab', '.*') // return true
* isMatch('ab', '.a') // return false
* isMatch('ab', '.b') // return true
* isMatch('aab', 'c*a*b') // return true
*/

思路：为目标字符串s和带匹配符的字符串r分别设置标记q和t，设s为 ”aab” r为 ”aacbaa*b”

/**
*类似通配符的匹配
* 说明：实现支持 '.' 和 '*' 的类似通配符的匹配，规则如下：
*
1. '.' 匹配任意单个字符
*
2. '*' 匹配零个或多个前面的元素
*
3. isMatch(s, r); s 是匹配的目标字符串，r 是带匹配符的字符串
*
4. r 的匹配应该覆盖 s
*
* 示例：
*
isMatch('aa','a') // return false
*
isMatch('aa','aa') // return true
*
isMatch('aaa','aa') // return false
*
isMatch('aa', 'a*') // return true
*
isMatch('aab', 'a*') // return false
*
isMatch('aa', '.*') // return true
*
isMatch('ab', '.*') // return true
*
isMatch('ab', '.a') // return false
*
isMatch('ab', '.b') // return true
*
isMatch('aab', 'c*a*b') // return true
*/
/**
*
* @param s 目标字符串
* @param r 带匹配符的字符串
* @param t 每次比较从r[t]开始
* @param slen 初始化s串的长度，避免每次计算
* @param rlen 初始化r串的长度，避免每次计算
* @return 返回结果
*/
public boolean isMatch (String s , String r , int t , int slen , int rlen) {
//初始化s串的标记位为0
int q = 0;
while (s.charAt(q) == r.charAt(t) || r.charAt(t) == '*' || r.charAt(t) == '.') {
if (r.charAt(t) == '*') {
//此时r[t]=="*",则判断r[t-1]是否与s[q]相等，如果相等则q一直向前走直到s[q]！=r[t-1]或s串匹配结束
while (r.charAt(t-1) == s.charAt(q) || r.charAt(t-1) == '.') {
q++;
//s串匹配到末尾说明匹配成功
if (q == slen) {
return true;
}
}
} else {
//此时s[q]=r[t]或r[t]="."，无论哪种情况，q都向前走一步
q++;
}
//每次循环t都要向前走一步
t++;
//s串匹配到末尾说明匹配成功
if (q == slen) {
return true;
}
//r串匹配到末尾,但s串还没有匹配完，说明匹配失败
if (t == rlen ) {
return false;
}
}
//本次循环结束，走到着说明没有匹配成功，t向前走一步以便下次r串从r[t]的位置开始匹配
t++;
//r串匹配到末尾,但s串还没有匹配完，说明匹配失败
if (t == rlen) {
return false;
}
//
if (r.charAt(t) == '*' || r.charAt(t) == '.') {
//
t++;
//
}
return isMatch(s , r , t , slen , rlen);
}