0044. 通配符匹配 [Hard] [Wildcard Matching].md

44. Wildcard Matching

Given an input string (s) and a pattern (p), 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).

Note:

• s could be empty and contains only lowercase letters a-z.
• p could be empty and contains only lowercase letters a-z, and characters like ? or *.

Example 1:

Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input:
s = "aa"
p = "*"
Output: true
Explanation: '*' matches any sequence.

Example 3:

Input:
s = "cb"
p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.

Example 4:

Input:
s = "adceb"
p = "*a*b"
Output: true
Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".

Example 5:

Input:
s = "acdcb"
p = "a*c?b"
Output: false

---

题目：通配符匹配。?匹配任意一个字符，*匹配任意n个字符。判断模式串p是否匹配s。

思路：参考Linear runtime and constant space solution。关键在于遇到星号时的处理，记录该星号的位置，以及当前s对应的指针，当s[i] != p[j]时，利用星号更新两个指针位置。

工程代码下载

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        int i = 0, j = 0, match = -1, star = -1;  // 记录星号的位置
        while(i < m){

            if(j < n && (s[i] == p[j] || p[j] == '?')){
				++i, ++j;
            }
            else if(j < n && p[j] == '*'){
                star = j++;  // 只更新模式串的指针(因为可以表示空字符)，记录星号的位置
                match = i;
            }
            else if(star != -1){
                j = star + 1;  // 如果遇到不匹配的情况，模式串回溯
                i = ++match;
            }
            else{
                return false;
            }
        }
        // 判断j指向的p位置后面是否只剩星号
        while(j < n && p[j] == '*')
            ++j;
        return j == n;
    }
};