如何判断含通配符'*'的两个字符串是否匹配？求递归解法思路

嘿，我完全懂这种试过各种方法却卡壳的感觉！其实这个带*的通配符匹配的递归解法，核心就是把复杂问题拆成一个个小的子问题，咱们一步步理清楚：

递归的关键是先明确终止条件，再拆分不同情况处理：

1. 先处理边界终止情况 #

这是递归的“出口”，必须先定义清楚：

• 如果s2已经遍历完（长度为0）：只有当s1也完全遍历完时，才说明匹配成功，返回True；否则返回False。
• 如果s1已经遍历完：此时需要检查s2剩下的所有字符是不是全是*（因为*可以匹配空字符串），是则返回True，否则False。

2. 分情况处理递归分支 #

接下来针对s2的当前字符，分两种核心场景处理：

场景A：当前s2字符不是* #

这种情况要求s1的当前字符必须和s2的当前字符完全相同，然后递归处理两个字符串去掉当前字符后的子串（也就是s1[1:]和s2[1:]）。

场景B：当前s2字符是* #

这是通配符的核心逻辑，*可以匹配任意字符串（包括空），所以我们有两种选择，只要其中一种能匹配成功就行：

• 选择1：让*匹配空字符串——直接跳过这个*，递归处理原s1和去掉*后的s2[1:]。
• 选择2：让*匹配s1的当前字符（并且可以继续匹配后面的字符）——递归处理去掉当前字符的s1[1:]和原s2。

按照上面的思路，几行代码就能实现基础版本：

def is_match(s1, s2):
    # 终止条件1：s2已空，检查s1是否也空
    if not s2:
        return not s1
    # 终止条件2：s1已空，检查s2剩余是否全为*
    if not s1:
        return all(c == '*' for c in s2)
    # 处理*的情况
    if s2[0] == '*':
        # 两种匹配路径，任意一种成功即可
        return is_match(s1, s2[1:]) or is_match(s1[1:], s2)
    else:
        # 非*字符必须严格匹配，再递归子问题
        return s1[0] == s2[0] and is_match(s1[1:], s2[1:])

上面的基础递归会有很多重复计算（比如同一个子串组合会被多次调用），可以用Python的lru_cache装饰器做记忆化，大幅提升效率：

from functools import lru_cache

@lru_cache(maxsize=None)
def is_match(s1, s2):
    if not s2:
        return not s1
    if not s1:
        return all(c == '*' for c in s2)
    if s2[0] == '*':
        return is_match(s1, s2[1:]) or is_match(s1[1:], s2)
    else:
        return s1[0] == s2[0] and is_match(s1[1:], s2[1:])

这个思路能覆盖所有用例的原因在于：它把所有可能的匹配路径都枚举了——无论是*的空匹配还是持续匹配，还是非通配符的严格匹配，再加上边界情况的处理，完全覆盖了题目要求的所有场景。

内容的提问来源于stack exchange，提问作者Pierre-Quentin Deguingand