题目重点：明确只支持.和后缀*的全串匹配，使用前缀DP处理空串与重复，避免指数回溯。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练.匹配任意单个code point，*重复前一个普通字符或.零次及以上；匹配整个text，不是搜子串。
- 不支持转义、括号、|、+、?或字符类；其余字符按字面，首*和连续**为非法pattern。
- 空串与空pattern合法输入；示例复用已验证的点星DP实现。
解题路线
- dp[i][j]为text前i字符与pattern前j字符是否全匹配。普通字符或.必须消费双方各一格，取dp[i−1][j−1]且当前字符可匹配。
- 当pattern[j−1]是*时，它和前一atom组成整体。有零次分支dp[i][j−2]；有至少一次且当前text字符匹配atom时取dp[i−1][j]，仍保留当前atom*以接后续字符。
- 不要把重复分支写成dp[i−1][j−2]，那只容许本次一个字符并跳过重复器，无法覆盖aa与a*。也不要让*直接匹配text字符，它只修饰前一个atom。
- 空串第一行需要传播成对的atom*跳过，例如a*b*可全取零次；普通atom不能匹配空。pattern首星或连续星预先拒绝，避免j−2访问错误。
- 每行依赖上一行与本行j−2，滚动两行足够；匹配最终dp[n][m]，不能遇到中途True就返回，那会把前缀匹配误作全串匹配。
- DP合并同一(i,j)的不同路径，从而避开重复回溯的指数展开，但状态总数仍为n×m。服务端处理不可信超大pattern还需长度/时间预算，线性空间不代表无限输入安全。
- 若扩展到一般regex，需要明确转义、捕获、贪婪、Unicode类别等语义；不能把此小语法实现声称替代语言自带完整正则库。
手动走一遍
aa与a*匹配；ab与.*匹配；空串与a*b*匹配；aab与c*a*b匹配。text=ab、pattern=a为False，因为必须消费整串。*a非法。
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]
复杂度
O((n+1)(m+1))时间，O(m+1)工作空间；输出布尔，无路径重建。空串仍需O(m)初始化。
易错点与追问
容易失分的边界
- 星号只重复一次。
- 只做前缀/子串搜索却说全匹配。
- 空串行没处理atom*零次链。
- 不说明简化语法就声称完整regex。
继续深挖
- 如何改为返回匹配路径？
- 加转义与字符类怎样tokenize？
- NFA实现与前缀DP有什么关系？
- 如何设置输入预算避免超大矩阵时间？
