Amazon Coding：Regex Matching，点号与星号怎样做完整匹配 DP？

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 只写regex matching，未公开元字符与full/substring匹配合同；本文采用经典点号/后缀星号的标准训练语法，不声称复原全部原题。
• 点号匹配任意一个字符，x*匹配零或更多x；字面字符直接比较，其他符号不扩展为Python正则功能。不支持转义、分组、加号、字符类。
• 非法开头星号与连续星号拒绝；整串匹配。源码text按Python字符遍历，换行也是普通字符；独立re参考样例只用a/b避免点号默认换行语义不同。

解题路线

1. 设D[i,j]表示text前i字符与pattern前j字符完整匹配。D[0,0]=true；空文本可跳过成对atom*，因此a*b*匹配空串，a*b不匹配。普通字符或点号需要当前匹配且D[i−1,j−1]。
2. 当前pattern[j−1]为星号时，零次重复取D[i,j−2]；若前一atom与text[i−1]匹配，至少一次可取D[i−1,j]，保持整个atom*不消耗让其继续重复。二者取OR；用j−1会错误丢掉repeat atom合同。
3. 只依上一行和当前行j−2，可压成两行。当前行从左至右算，让零次重复的状态已存在；每个text字符必须新建false行，不能让上一轮true状态泄漏。
4. 先验证pattern语法再访问j−2，避免开头星号越界；空pattern只匹配空text。DP避免反复探索同一(i,j)导致指数回溯，但这是受限语法算法，不是完整正则库实现。
5. 独立参考用标准库re.fullmatch对受限a/b/./*合法模式核对，不用同一DP参考。生产输入若变用户提供全语法，需选正则引擎/超时/长度预算并明确ReDoS风险，不能继续把本DP套捕获组或反向引用。

手动走一遍

text=aab，pattern=c*a*b：c*零次，a*两次，b一次，结果true。text=ab，pattern=.*结果true；pattern=.只消费一个字符，结果false。text为空、pattern=a*b*为true；pattern=*a必须拒绝而不是当false掩盖非法语法。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def full_match(text, pattern):
    """Only '.' and postfix '*' are special; match the entire string."""
    if pattern.startswith('*') or '**' in pattern:
        raise ValueError('star must follow a non-star atom')
    m = len(pattern)
    previous = [False] * (m+1)
    previous[0] = True
    for j in range(2, m+1):
        if pattern[j-1] == '*':
            previous[j] = previous[j-2]
    for char in text:
        current = [False] * (m+1)
        for j in range(1, m+1):
            if pattern[j-1] == '*':
                atom = pattern[j-2]
                current[j] = current[j-2] or ((atom == '.' or atom == char) and previous[j])
            else:
                current[j] = (pattern[j-1] == '.' or pattern[j-1] == char) and previous[j-1]
        previous = current
    return previous[m]

复杂度

n字符、m模式字符：O(nm)时间、O(m)工作空间。输出boolean；不返回匹配跨度、捕获组或最短/最长子串。

易错点与追问

容易失分的边界

• 完整匹配误写为search。
• 星号只匹配任意一个字符。
• 忽略零次重复。
• 复用current数组留下状态。
• 擅自支持全部正则语法。

继续深挖

• 如果只要任意子串匹配，边界状态怎样改？
• 通配符glob的星号为何不同？
• 增加捕获组为何不只是多一个if？
• 输入很长如何设置资源预算？