leetcode 44. Wildcard Matching 解题思路分析

题目大意：

通配符匹配

给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。

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

两个字符串完全匹配才算匹配成功。

说明:

• s 可能为空，且只包含从 a-z 的小写字母。
• p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。

示例 1:

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:

输入:
s = "aa"
p = "*"
输出: true
解释: '*' 可以匹配任意字符串。

示例 3:

输入:
s = "cb"
p = "?a"
输出: false
解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。

示例 4:

输入:
s = "adceb"
p = "*a*b"
输出: true
解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".

示例 5:

输入: s = "acdcb" p = "a*c?b" 输入: false

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=44

解题思路：

这是一道通配符匹配的题，？代表任意一个小写字母，*则代表了0-多个小写字母。难点在于*适配的位数不定，这样我们就不能将字符串s和匹配字符p按照位数一一对应的去比对了。

这道题解题的关键就在于如何巧妙的运用 ‘*’ ，我们先来看匹配字符串p，如果我们将p中的所有星号都忽略掉，那么p就会变成N段有小写字母和问号组成的多个子字符串。比如：p=”abcd*fg?h**ijk”;去掉星号之后就会剩下[abcd，fg?h，ijk]三个子字符串，由于星号可以匹配0-多位，所以问题就简化为，字符串s中是否顺序包含上述所有的子字符串。

不过还有两点需要注意的地方：

第一，关于p去除星号之后的多个子字符串的首尾两个”abcd”和”ijk”，我们必须保证他们分别必须匹配上字符串s对应的首尾位置。而对于中间的所有子字符串，由于两边都有星号的庇护，所以无需考虑匹配s时对应的位置，只要保证所有的字符串能够在s中顺序被找到即可（区间不能有重叠）。分析至此，我们发现，如果匹配字符串能够是以星号开头并以星号结尾的话，那么我们处理起来就会更加方便，所以我们可以考虑先做剪枝操作，将p和s的首尾非星号字符都先匹配掉。

第二，关于问号的匹配方法。现在问题只剩下了p的某个子字符串是否能够在s中被找到。子字符串可能出现的情况分为以下几种，

1. 只包含小写字母的情况。这在s中查找比较简单。如果匹配成功，我们可以将s中此字符串以及之前的所有字符全部删掉，以便后续匹配。
2. 以小写字母开头，中间或末尾包含问号。这和第一种情况比较类似，只不过问号可以匹配任意字符而已。同样匹配后删除s中此字符串以及之前的所有字符。
3. 以问号开头，后续包含小写字母。我们需要先计算出开头连续出现的问号的个数offset，然后以最先出现的小写字母为起点去s中匹配，此时最先出现的小写字母在s中的位置必须相隔s开头至少offset位数。同样匹配后删除s中此字符串以及之前的所有字符。
4. 子字符串全部是问号。这种情况也不复杂，只需要按照问号的个数删除s中前几位即可。

思路分析完了，我们总结下流程：

1. 先剪枝，将p中首尾非星号字符逐一匹配，剩下一个以星号开头并以星号结尾的p。如果p中根本没有星号的话，那么剪枝结束后也就知道结果了。
2. 用星号分割p，生成多个只含有小写字母及问号的子字符串
3. 按照顺序匹配s中是否包含上述子字符串

完整代码：

public boolean isMatch(String s, String p) {
    // 匹配掉p开头的所有非星号字符
	while (s.length() > 0 && p.length() > 0) {
		if (p.charAt(0) == '*') {
			break;
		}
        // 匹配成功则将p和s的该位移除
		if (p.charAt(0) == '?' || p.charAt(0) == s.charAt(0)) {
			s = s.substring(1);
			p = p.substring(1);
		} else {
        // 匹配失败，返回false
			return false;
		}
	}
    // 匹配掉p结尾的所有非星号字符
	while (s.length() > 0 && p.length() > 0) {
		if (p.charAt(p.length() - 1) == '*') {
			break;
		}
        // 匹配成功则将p和s的该位移除
		if (p.charAt(p.length() - 1) == '?' || p.charAt(p.length() - 1) == s.charAt(s.length() - 1)) {
			s = s.substring(0, s.length() - 1);
			p = p.substring(0, p.length() - 1);
		} else {
        // 匹配失败，返回false
			return false;
		}
	}
    // 将p用星号分割。注意星号为特殊字符需要转义一下
	String[] pa = p.split("\\*");
    // 分别匹配ps中每个子字符串
	for (String ps : pa) {
        // 子字符串为空则忽略
		if ("".equals(ps)) {
			continue;
		}
        // 如果子字符串长度大于s，则返回false
		if (ps.length() > s.length()) {
			return false;
		}
        // 定义一个变量charOffset，记录子字符串开头的问号个数
		int charOffset = 0;
        // 检查子字符串开头的问号个数
		if (ps.startsWith("?")) {
			for (char c : ps.toCharArray()) {
				if (c == '?') {
					charOffset++;
				} else {
					break;
				}
			}
		}
        // 如果问号个数等于子字符串长度，说明该子字符串全部是问号
        // 则删除s的开头相应的位数。同时将p中的该子字符串替换为空
		if (charOffset == ps.length()) {
			p = p.replaceFirst(Pattern.quote(ps), "");
			s = s.substring(charOffset);
			continue;
		}
        // 如果子字符串中包含小写字母，则查找该子字符串在s中首次出现的位置
		int startIndex = isContainString(s, ps, charOffset);
        // 如果startIndex为-1，说明s中不存在该子字符串，返回false
		if (startIndex == -1) {
			return false;
		}
        // 如果s中存在该子字符串，则将s中此子字符串及其之前的全部字符删去
		p = p.replaceFirst(Pattern.quote(ps), "");
        // 同时将s中此子字符串替换为空，继续循环下一个子字符串
		s = s.substring(startIndex + ps.length());
	}
    // 子字符串全部循环之后如果s已经为空，说明匹配成功。
    // 另外，此时p应该也为空或者只剩下星号字符。
	if ("".equals(s)) {
		return true;
	} else {
        // 如果s还有剩余字符，那么看p是否还有剩余，由于p剩下的只可能是星号
        // 所以，只要p不为空则返回true，否则返回false
		if (!"".equals(p)) {
			return true;
		} else {
			return false;
		}
	}
}
// 查看s中是否包含p的子字符串
private int isContainString(String s, String p, int charOffset) {
	int sLength = s.length();
	int pLength = p.length();
    // 如果子字符串的长度大于s，返回-1
	if (pLength > sLength) {
		return -1;
	}
    // 将子字符串p的开头问号都删掉
	p = p.substring(charOffset);
    // 重新计算p的长度
	pLength = p.length();
    // 循环字符串s
	for (int i = charOffset; i < sLength; i++) {
        // 先找到s中与p的首字符相同的字符的位置
		if (s.charAt(i) == p.charAt(0) && sLength - i >= pLength) {
            // 如果找到，开始循环p
			for (int j = 0; j < pLength; j++) {
                // 如果p的当前字符不是问号或者不等同于s对应位置的字符，
                // 则退出p循环，继续在s中寻找下一个与p的首字符相同的字符的位置
				if (p.charAt(j) != '?' && p.charAt(j) != s.charAt(i + j)) {
					break;
				} else {
                // 如果循环到最后一位都能匹配上，则说明匹配成功，返回对应的位置。
                // 注意循环开始前已将问号去除，所以位置不是i，而是i减去开头问号的长度。
					if (j == pLength - 1) {
						return i - charOffset;
					}
				}
			}

		}
	}
	return -1;
}

本解法用时为36毫秒

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-44-wildcard-matching-解题思路分析/