Wildcard Matching
最后更新于：2022-04-02 01:07:56
# Wildcard Matching
### Source
- leetcode: [Wildcard Matching | LeetCode OJ](https://leetcode.com/problems/wildcard-matching/)
- lintcode: [(192) Wildcard Matching](http://www.lintcode.com/en/problem/wildcard-matching/)
~~~
Implement wildcard pattern matching with support for '?' and '*'.
'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).
Example
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false
~~~
### 题解1 - [DFS](# "Depth-First Search, 深度优先搜索")
字符串的通配实现。'`?`'表示匹配单一字符，'`*`'可匹配任意多字符串(包含零个)。要匹配的字符串设为`s`, 模式匹配用的字符串设为`p`，那么如果是普通字符，两个字符串索引向前推进一位即可，如果`p`中的字符是`?`也好办，同上处理，向前推进一位。所以现在的关键就在于如何处理'`*`', 因为`*`可匹配0, 1, 2...个字符，所以遇到`*`时，`s`应该尽可能的向前推进，注意到`p`中`*`后面可能跟有其他普通字符，故`s`向前推进多少位直接与`p`中`*`后面的字符相关。同时此时两个字符串的索引处即成为回溯点，如果后面的字符串匹配不成功，则`s`中的索引向前推进，向前推进的字符串即表示和`p`中`*`匹配的字符个数。
### Java
~~~
public class Solution {
/**
* @param s: A string
* @param p: A string includes "?" and "*"
* @return: A boolean
*/
public boolean isMatch(String s, String p) {
if (s == null || p == null) return false;
if (s.length() == 0|| p.length() == 0) return false;
return helper(s, 0, p, 0);
}
private boolean helper(String s, int si, String p, int pj) {
// index out of range check
if (si == s.length() || pj == p.length()) {
if (si == s.length() && pj == p.length()) {
return true;
} else {
return false;
}
}
if (p.charAt(pj) == '*') {
// remove coninuous *
while (p.charAt(pj) == '*') {
pj++;
// index out of range check
if (pj == p.length()) return true;
}
// compare remaining part of p after * with s
while (si < s.length() && !helper(s, si, p, pj)) {
si++;
}
// substring of p equals to s
return si != s.length();
} else if (s.charAt(si) == p.charAt(pj) || p.charAt(pj) == '?') {
return helper(s, si + 1, p, pj + 1);
} else {
return false;
}
}
}
~~~
### 源码分析
其中对`*`的处理和递归回溯是这段代码的精华。
### 复杂度分析
最坏情况下需要不断回溯，时间复杂度 O(n!)×O(m!)O(n!) \times O(m!)O(n!)×O(m!), 空间复杂度 O(1)O(1)O(1)(不含栈空间)。
### Reference
- Soulmachine 的 leetcode 题解
-
';