通配符模式匹配问题：设计高效算法验证字符串与模式完全匹配

这是个经典的字符串匹配问题，要求模式中的?匹配任意单个字符，*匹配任意长度的字符（包括零），且必须完全匹配整个输入字符串，不是部分匹配。下面分享一个高效的贪心算法，时间复杂度O(n+m)，空间复杂度O(1)，比常规的动态规划解法更省内存。

算法思路（贪心双指针） #

核心思路是用双指针遍历字符串和模式，遇到*时记录位置，后续不匹配时回溯，让*匹配更多字符：

• 初始化两个指针 i（遍历输入字符串）、j（遍历模式），以及两个回溯标记 last_str_pos、last_pat_pos（记录遇到*时的位置）。
• 遍历字符串：
  1. 如果当前字符匹配（字符串字符等于模式字符，或模式字符是?），同时移动i和j。
  2. 如果遇到*，记录当前i和j的位置（last_str_pos = i，last_pat_pos = j），然后只移动模式指针j（尝试让*匹配0个字符）。
  3. 如果当前不匹配，但之前遇到过*：回溯到*的下一个位置（j = last_pat_pos + 1），同时让字符串指针前进一位（i = last_str_pos + 1），更新last_str_pos，相当于让*多匹配一个字符。
  4. 如果既不匹配也没有*可以回溯，直接返回No Match。
• 字符串遍历完成后，还要处理模式剩余的字符：剩余的必须全是*才算匹配（因为*可以匹配零个字符）。

代码实现（Python） #

def is_wildcard_match(s: str, p: str) -> str:
    i = j = 0
    n, m = len(s), len(p)
    last_str_pos = -1
    last_pat_pos = -1

    while i < n:
        # 字符匹配或者是?
        if j < m and (s[i] == p[j] or p[j] == '?'):
            i += 1
            j += 1
        # 遇到*，记录位置
        elif j < m and p[j] == '*':
            last_str_pos = i
            last_pat_pos = j
            j += 1
        # 不匹配但有*可以回溯
        elif last_pat_pos != -1:
            last_str_pos += 1
            i = last_str_pos
            j = last_pat_pos + 1
        # 完全不匹配
        else:
            return "No Match"
    
    # 处理模式剩余的*
    while j < m and p[j] == '*':
        j += 1
    
    return "Match" if j == m else "No Match"

示例验证 #

我们用题目里的测试用例来验证：

• 输入：string = "xyxzzxy", pattern = "x***y" → 输出Match：开头x匹配，结尾y匹配，中间的***可以匹配中间的yxzzx部分。
• 输入：string = "xyxzzxy", pattern = "x***x" → 输出No Match：字符串结尾是y，模式最后是x，没有*或?能匹配这个差异。
• 输入：string = "xyxzzxy", pattern = "x***x?" → 输出Match：x匹配开头，***匹配yxzz，x匹配字符串倒数第二个字符，?匹配最后一个y。
• 输入：string = "xyxzzxy", pattern = "*" → 输出Match：*可以匹配任意长度的字符串，包括整个输入。

内容的提问来源于stack exchange，提问作者Raheel