https://www.lintcode.com/problem/wildcard-matching/description?_from=ladder&&fromId=6
| 日期 | 是否一次通过 | comment |
|---|---|---|
| 2019-05-19 20:20 | N |
判断两个可能包含通配符“？”和“*”的字符串是否匹配。匹配规则如下：
- '?' 可以匹配任何单个字符。
- '*' 可以匹配任意字符串（包括空字符串）。
两个串完全匹配才算匹配成功。
image.png
分析：（转自链接）
假设我们用两个指针分别指向s和p字符串中要匹配的位置，首先分析下通配符匹配过程中会有哪些情况是成功：
-
s的字符和p的字符相等 -
p中的字符是?，这时无论s的字符是什么都可以匹配一个 -
p中遇到了一个*，这时无论s的字符是什么都没关系 - 之前的都不符合，但是
p在之前的位置有一个*，我们可以从上一个*后面开始匹配
5.s已经匹配完，但是p后面还有很多连续的*
这里1和2的情况比较好处理，关键在于如何处理3和4的情况。当我们遇到一个*时，因为之后可能要退回至该位置重新匹配，我们要将它的下标记录下来，比如idxStar。但是，当我们连续遇到两次4的情况，如何保证我还是能继续匹配s，而不是每次都退回idxStar+1导致循环呢？所以我们还要记录一个idxMatch，用来记录用上一个*连续匹配到的s中的下标。最后，对于情况5，我们用一个循环跳过末尾的*跳过就行了。
public boolean isMatch(String str, String pattern) {
int idxStr = 0, idxPat = 0, idxStar = -1, idxMatch = 0;
while(idxStr < str.length()){
// 当两个指针指向完全相同的字符时，或者p中遇到的是?时
if(idxPat < pattern.length() && (str.charAt(idxStr) == pattern.charAt(idxPat) || pattern.charAt(idxPat) == '?')){
idxPat++;
idxStr++;
// 如果字符不同也没有?，但在p中遇到是*时，我们记录下*的位置，但不改变s的指针
} else if(idxPat < pattern.length() && pattern.charAt(idxPat)=='*'){
idxStar = idxPat;
idxPat++;
//遇到*后，我们用idxmatch来记录*匹配到的s字符串的位置，和不用*匹配到的s字符串位置相区分
idxMatch = idxStr;
// 如果字符不同也没有?，p指向的也不是*，但之前已经遇到*的话，我们可以从idxmatch继续匹配任意字符
} else if(idxStar != -1){
// 用上一个*来匹配，那我们p的指针也应该退回至上一个*的后面
idxPat = idxStar + 1;
// 用*匹配到的位置递增
idxMatch++;
// s的指针退回至用*匹配到位置
idxStr = idxMatch;
} else {
return false;
}
}