🥇Hard

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

  1. '?' 可以匹配任何单个字符。
  2. '*' 可以匹配任意字符串（包括空字符串）。
  3. 两个字符串完全匹配才算匹配成功。

说明:
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

思路

这道题做的时候只能想到一些特殊的情况：

  1. 如果两个字符串都没有通配符，就直接比较两个字符串是否相等
  2. 如果两个字符串中有一个是"*"的话，一定返回True
  3. 分别从头遍历字符串，如果一个字符串A中发现有"*"，那就遍历另一个字符串B直到B中的某一个字符与A中"*"后一个字符相等，然后继续对比即可，如果后续没有对上，那就返回False
  4. 如果字符串中出现"?",两个字符串分别跳过这个字符，继续对比

这样考虑没有问题，但是情况太多，写起来太过复杂，下面是尝试的代码，但是没有考虑有可能”*”、”?”匹配的是空字符串的情况。但是已经写不下去了，算法要好好加强啊，太差了😤

def isMatch(s, p):
    if '*' not in s and '*' not in p and '?' not in s and '?' not in p:
        if s == p:
            return True
        else:
            return False
    if s == '*' * len(s) or p == '*' * len(p):
        return True
    i = 0
    j = 0
    while i < len(s) and j < len(p):
        if s[i] == '*':
            while p[j] != s[i + 1]:
                j += 1
                if j == len(p) - 1 and p[j] != s[i + 1]:
                    return False
        if p[j] == '*':
            while s[i] != p[j + 1]:
                i += 1
                if i == len(s) - 1 and s[i] != p[j + 1]:
                    return False
        if s[i] == '?' or p[j] == '?':
            i += 1
            j += 1
        if s[i] != p[j]:
            return False
    return True

题解

看了一下别人提供的解法：

双指针

class Solution:
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        i = 0
        j = 0
        start = -1
        match = 0
        while i < len(s):
            # 一对一匹配,匹配成功一起移
            if j < len(p) and (s[i] == p[j] or p[j] == "?"):
                i += 1
                j += 1
            # 记录p的"*"的位置,还有s的位置
            elif j < len(p) and p[j] == "*":
                start = j
                match = i
                j += 1
            # j 回到 记录的下一个位置
            # match 更新下一个位置
            # 这不代表用*匹配一个字符
            elif start != -1:
                j = start + 1
                match += 1
                i = match
            else:
                return False
         # 将多余的 * 直接匹配空串
        return all(x == "*" for x in p[j:])