# LintCode 通配符匹配分析

'?' 可以匹配任何单个字符。 '*' 可以匹配任意字符串（包括空字符串）。

isMatch("aa","a") → false isMatch("aa","aa") → true isMatch("aaa","aa") → false isMatch("aa", "") → true isMatch("aa", "a") → true isMatch("ab", "?") → true isMatch("aab", "ca*b") → false

# 分析

## 方法一：

```public class Solution {
/**
* @param s: A string
* @param p: A string includes "?" and "*"
* @return: A boolean
*/
public boolean isMatch(String s, String p) {
boolean[][] match=new boolean[s.length()+1][p.length()+1];
match[s.length()][p.length()]=true;

for(int i=p.length()-1;i>=0;i--){
if(p.charAt(i)!='*')
break;
else
match[s.length()][i]=true;
}
for(int i=s.length()-1;i>=0;i--){
for(int j=p.length()-1;j>=0;j--){
if(s.charAt(i)==p.charAt(j)||p.charAt(j)=='?')
match[i][j]=match[i+1][j+1];
else if(p.charAt(j)=='*')
match[i][j]=match[i+1][j]||match[i][j+1] || match[i+1][j+1];
else
match[i][j]=false;
}
}
return match[0][0];
}
}

/*aab  s

a**b   p

m[i][j]

m[2][3] = m[3][4]
m[2][2] = if * == b:m[3][3]
if * == empty m[2][3]
if * == 其他 m[3][2]

*/```

## 方法二

```public class WildcardMatching {
public boolean isMatch(String str, String pattern) {
int s = 0;
int p = 0;
int sMatch = -1;//*匹配s中的字符的终止位置
int starIdx = -1;//最近一个*出现的位置
while (s < str.length()){
if (p < pattern.length()  && (pattern.charAt(p) == '?' || str.charAt(s) == pattern.charAt(p))){
s++;
p++;
}
// * found, only advancing pattern pointer，，先让* 作为empty出现，所以s不需要++
else if (p < pattern.length() && pattern.charAt(p) == '*'){
starIdx = p;//record the index of *
sMatch = s;//record the * 匹配的s中的位置
p++;
}
//last pattern pointer was *, advancing string pointer，用*去匹配当前的串
else if (starIdx != -1){
p = starIdx + 1;//只能用* 去匹配，所以p要回到*后面一个元素开始判断
sMatch++;//被*匹配了
s = sMatch;
}
//current pattern pointer is not star, last patter pointer was not *
//characters do not match
else return false;
}

//check for remaining characters in pattern
while (p < pattern.length() && pattern.charAt(p) == '*')
p++;

return p == pattern.length();
}
}```

381 篇文章35 人订阅

0 条评论

## 相关文章

### go基础编程 day-2

零值并不等于空值，而是当变量声明为某种来兴后的默认零值，通常情况下默认值为0，bool为false，string为空字符串。

1092

### Java之分支和循环

Java中的分支语句： if语句： if语句的四种写法： 　　（1） 　　if(表达式_布尔值) { 　　... 　　} 　　（2） 　　if(表达式_布...

3089

2864

2133

1003

### c语言格式大整理

1、C语言中，非零值为真，真用1表示；零值为假，假用0表示。 2、转义字符参考： \a 蜂鸣，响铃  \b 回退：向后退一格 ...

5297

1492

### 【必读】C语言基础知识大全

C语言程序的结构认识 ﻿用一个简单的c程序例子，介绍c语言的基本构成、格式、以及良好的书写风格，使小伙伴对c语言有个初步认识。﻿ 例1：计算两个整数之和的c程...

5558

3197

2302