kimi-for-coding 在「实现正则表达式」的评测结果

这是该 AI 模型在此测试用例上的详细评测结果。

基本信息

  • 模型名称：kimi-for-coding
  • 用例名称：实现正则表达式
  • 测试类型：文本生成
  • 评测维度：代码生成

系统提示词（System Prompt）

这是给 AI 模型的背景设定和角色指令：

你是一名资深 Python 开发工程师，擅长字符串处理与算法设计。 回答要求： 1. 先简要分析匹配逻辑（字符对齐、'?' 的语义），再给出实现代码。 2. 代码风格符合 PEP 8，函数需包含清晰的 docstring 说明参数与返回值。 3. 对关键逻辑（如长度校验、'?' 匹配分支）添加行内注释，便于阅读。 4. 给出至少 3 个测试用例验证代码正确性，覆盖正常情况与边界情况。

用户提示词（User Prompt）

这是用户给 AI 模型的具体任务要求：

请用 Python 实现一个简单的字符串模式匹配函数，函数签名如下：

任务要求

AI 模型需要满足以下要求：

  1. 正确实现 '?' 匹配恰好一个任意字符、'*' 匹配零个或多个任意字符的语义，通过所有示例用例
  2. 正确处理边界情况：空字符串 s 或 p、模式全为 '*'、连续多个 '*'、'*' 与 '?' 混合
  3. 采用动态规划或贪心双指针等高效算法，时间复杂度不超过 O(m×n)，并在代码注释或说明中给出复杂度分析
  4. 代码结构清晰，符合 PEP 8 规范，关键逻辑（如 DP 转移方程或指针回溯逻辑）有必要注释
  5. 能正确处理连续多个 '*' 的情况（等价于单个 '*'），不因此产生错误或性能退化

评测结果

综合得分

该模型在此用例的得分为：93.4 分（满分 100 分），已通过

基础难度评测结果

  • 得分：93.4 分
  • 通过状态：已通过

模型生成产物

以下是该模型针对此任务的实际生成内容：

由于输入中函数签名被截断，这里基于“仅含 `?` 通配符”的常见需求，采用如下签名进行实现： ```python def simple_match(pattern: str, text: str) -> bool: ``` ### 一、匹配逻辑简要分析 1. **长度对齐**：字符 `?` 只能匹配**任意单个字符**，不具备扩展或收缩长度的能力。因此如果 `pattern` 与 `text` 长度不同，可直接判定不匹配。 2. **逐字符比对**：在长度相等的前提下，按索引从左到右逐个字符比较。 - 若 `pattern[i] == '?'`，则无论 `text[i]` 是什么字符，都认为当前位置匹配成功。 - 若 `pattern[i]` 为普通字符，则必须与 `text[i]` 严格相等，否则立即返回 `False`。 3. **全遍历成功**：当所有位置均满足上述规则时，返回 `True`。 --- ### 二、实现代码 ```python def simple_match(pattern: str, text: str) -> bool: """判断文本串 text 是否与仅含 '?' 通配符的模式串 pattern 匹配。 '?' 可以匹配任意单个字符，但 pattern 与 text 的长度必须严格一致。 Args: pattern: 模式字符串，可包含普通字符和 '?'。 text: 待匹配的目标字符串。 Returns: bool: 匹配成功返回 True，否则返回 False。 """ # 长度校验：'?' 仅匹配单个字符，长度不等则必然不匹配 if len(pattern) != len(text): return False # 逐字符对齐比较 for p_char, t_char in zip(pattern, text): if p_char == '?': # '?' 匹配任意单个字符，直接跳过当前位置 continue if p_char != t_char: # 普通字符未对齐，匹配失败 return False # 所有位置均满足匹配规则 return True # ------------------- 测试用例 ------------------- if __name__ == "__main__": # 用例 1：正常匹配，'?' 匹配单个字符 assert simple_match("a?c", "abc") is True print("Test 1 passed: a?c == abc") # 用例 2：普通字符不匹配 assert simple_match("abc", "abd") is False print("Test 2 passed: abc != abd") # 用例 3：边界情况——空字符串 assert simple_match("", "") is True print("Test 3 passed: empty strings match") # 用例 4：边界情况——长度不等（无法通过 '?' 弥补） assert simple_match("a?", "a") is False print("Test 4 passed: length mismatch returns False") # 用例 5：全为 '?' 的极端情况 assert simple_match("???", "123") is True print("Test 5 passed: ??? matches 123") print("All tests passed.") ``` **代码要点说明：** - 通过 `len()` 前置拦截，避免无效遍历。 - `zip()` 保证在长度相等时逐对取出字符，逻辑清晰。 - 对 `?` 的分支使用 `continue` 而非嵌套 `else`，减少缩进，提高可读性。

AI 评审点评

以下是 AI 评审对该模型输出的点评：

【CLAUDE】该回答在函数签名被截断的情况下，合理假设并明确说明了实现目标，展现了良好的工程判断力。实现代码逻辑清晰正确，代码风格规范，注释充分，测试用例覆盖全面（5个，超出要求），整体质量较高，完全满足题目各项要求。 【GEMINI】这是一份高质量的回答。面对截断的输入，模型展现了良好的专业素养，通过明确假设来消除歧义。代码实现简洁高效，使用了 Pythonic 的 zip 函数，注释与文档完备，测试用例充分，完全满足了资深工程师的角色设定要求。 【KIMI】该候选输出在函数签名被截断的情况下，基于常见需求合理推断并实现了仅含'?'通配符的字符串模式匹配。逻辑完全正确，代码风格规范，注释清晰，测试用例覆盖充分（5个，含边界情况）。整体表现优秀，是一篇高质量的算法实现回答。

进阶难度评测结果

  • 得分：92.9 分
  • 通过状态：已通过

模型生成产物

以下是该模型针对此任务的实际生成内容：

## 一、匹配逻辑与边界分析 全串匹配下，困难点只在 `*`：它可匹配 **0 到任意多个** 字符，因此遇到失配时需要"反悔"——让最近的那个 `*` 多吞掉一个字符再重试。优先级与边界如下： - 字面字符 / `?`：必须消耗 `s` 中恰好一个字符；`s` 已空而模式还剩非 `*` 字符 → 失败（如 `("", "?")`）。 - `*`：先按"匹配空串"处理（贪心），记录位置；后续若失配再回溯，让它多匹配一个字符。 - 连续多个 `*`：与单个 `*` 等价（`***` ≈ `*`），算法天然兼容。 - 结束条件：`s` 扫描完后，`p` 剩余部分必须 **全为 `*`**（`*` 可匹配空串），否则失败（如 `("aa", "a")`、`("acdcb", "a*c?b")`）。 下面给出**贪心双指针**实现（空间最优），并附 DP 转移方程作对照。 ## 二、实现代码（贪心双指针，O(1) 空间） ```python def is_match(s: str, p: str) -> bool: """通配符全串匹配：'?' 匹配单字符，'*' 匹配任意字符串（含空串）。""" i = j = 0 # i 扫描字符串 s，j 扫描模式 p star = -1 # 最近一次 '*' 在 p 中的下标；-1 表示尚未遇到 '*' ss = 0 # 该 '*' 当前匹配到 s 的位置（回溯时从此处继续） while i < len(s): # 1) 字面字符相等，或 '?' 匹配任意单字符：双双前进 if j < len(p) and (p[j] == s[i] or p[j] == "?"): i += 1 j += 1 # 2) 遇到 '*'：记录位置，先假设 '*' 匹配空串，模式指针前进 elif j < len(p) and p[j] == "*": star = j ss = i # 记下 '*' 开始尝试匹配 s 的位置 j += 1 # 3) 当前字符失配，但之前有 '*'：让 '*' 多吞掉 s 的一个字符再重试 elif star != -1: j = star + 1 # 模式回退到 '*' 之后一位 ss += 1 # '*' 多匹配一个字符 i = ss # 4) 失配且没有 '*' 可回溯：彻底失败 else: return False # s 已耗尽：p 剩余字符必须全是 '*'（'*' 可匹配空串） while j < len(p) and p[j] == "*": j += 1 return j == len(p) # ---------------- 自测 ---------------- if __name__ == "__main__": cases = [ ("aa", "a", False), ("aa", "*", True), ("cb", "?a", False), ("adceb", "*a*b", True), ("acdcb", "a*c?b", False), ("", "", True), ("", "*", True), ("", "?", False), ("abc", "***", True), ("abc", "*?*", True), ] for s, p, expected in cases: assert is_match(s, p) == expected, (s, p, is_match(s, p)) print("all passed") ``` ## 三、复杂度说明 设 `m = len(s)`，`n = len(p)`： - **时间复杂度**：最坏 `O(m · n)`（极端构造下 `*` 反复回溯）；实际/均摊通常接近线性 `O(m + n)`，因为每轮循环要么推进 `i`，要么推进 `ss`（等价于推进 `i`），要么推进 `j`。 - **空间复杂度**：`O(1)`，仅用若干整型指针。 ## 四、对照：DP 转移方程（同样可行） 令 `dp[i][j]` 表示 `s[:i]` 与 `p[:j]` 是否匹配： - 初始：`dp[0][0] = True`；`dp[0][j] = dp[0][j-1]` 当且仅当 `p[j-1] == '*'`。 - 转移： - 若 `p[j-1] == '*'`：`dp[i][j] = dp[i][j-1] or dp[i-1][j]`（`*` 匹配空串 / 多匹配一个字符）。 - 若 `p[j-1] == '?'` 或 `p[j-1] == s[i-1]`：`dp[i][j] = dp[i-1][j-1]`。 - 否则 `dp[i][j] = False`。 - 复杂度：时间 `O(m...

AI 评审点评

以下是 AI 评审对该模型输出的点评：

【KIMI】候选输出是一份高质量的通配符匹配实现，选择了空间最优的贪心双指针算法，逻辑正确，代码规范，注释完整。所有示例和边界用例均能正确处理。主要不足在于：仅实现了贪心双指针而未提供完整的 DP 代码实现（虽然给出了转移方程），与题目要求 '优先考虑使用动态规划（DP）或贪心双指针实现' 相比，对 DP 的呈现不够完整；变量命名可读性有提升空间。整体而言，该实现是正确、高效且可维护的。

困难难度评测结果

  • 得分：92.9 分
  • 通过状态：已通过

模型生成产物

以下是该模型针对此任务的实际生成内容：

下面给出一个完整实现：Part 1 用**二维 DP**实现 `is_match`（并附记忆化递归对照思路）；进阶用 `SimpleRegex` 类，把**模式解析（compile）**与**匹配执行（match）**彻底分开，并支持字符类 `[abc]` / `[^abc]` / `[a-z]`。 --- ## 一、算法思路说明 ### 1. 优先级与状态转移规则 `*` 是**后缀量词**，优先级最高，且必须绑定到**紧邻的前一个原子**（普通字符 / `.` / 字符类）。因此 `a*`、`.*`、`[a-z]*` 都应被看成一个整体 token，`*` 不能单独存在。 把模式切成 token 序列后，设： > `dp[i][j]` = `s` 的前 `i` 个字符 `s[:i]`，能否被前 `j` 个 token **完全匹配**。 转移方程（看第 `j` 个 token `t = tokens[j-1]`）： | token 类型 | 转移 | |---|---| | 必须出现一次 (`one`) | `dp[i][j] = dp[i-1][j-1] and t.matches(s[i-1])`（要求 `i≥1`）| | 零或多次 (`star`) | ① **零次**：`dp[i][j-1]`（丢掉该 token）② **一次或多次**：`dp[i-1][j] and t.matches(s[i-1])`（重复消耗当前 `*` token，注意是 `dp[i-1][j]` 而非 `dp[i-1][j-1]`）| 边界：`dp[0][0] = True`；答案为 `dp[len(s)][len(tokens)]`。 > Part 1 的原始写法里 `*` 单独占一个模式位，等价写法是“零次用 `dp[i][j-2]`、多次用 `dp[i-1][j]`”，本质相同。 ### 2. 选型：递归回溯 vs 动态规划 - **纯回溯**：`*` 每格都有“匹配 0 / 1 / 多 次”分支，形如 `a*a*a*a*` 对 `aaaa` 会产生**指数级**爆炸，且大量重复子问题。 - **记忆化递归（自顶向下）**：用 `(i,j)` 做 key 缓存，把重复子问题压掉，复杂度降到多项式，可读性强。 - **表格 DP（自底向上）**：与记忆化同阶，无递归栈开销、易做滚动数组优化，**作为主实现**。 结论：选用 **DP**（Part 1 用经典二维 DP；`SimpleRegex` 用 token 序列 DP）。 --- ## 二、完整可运行代码 ```python from __future__ import annotations from dataclasses import dataclass, field from typing import List, Set # ============================================================ # Part 1：基础正则匹配（仅支持 '.' 与 '*'，全串匹配） # ============================================================ def _validate_basic(p: str) -> None: """校验 Part 1 模式的合法性。""" if p and p[0] == "*": raise ValueError("非法模式：'*' 不能出现在开头（无前置原子）") for k in range(1, len(p)): # 连续的 '*'：第二个 '*' 的前一个仍是 '*'，说明没有可绑定的原子 if p[k] == "*" and p[k - 1] == "*": raise ValueError(f"非法模式：位置 {k} 出现连续的 '*'") def is_match(s: str, p: str) -> bool: """ 判断模式 p 是否【全串】匹配字符串 s。 语法：'.' 匹配任意单字符；'x*' 匹配零个或多个 x（x 可为 '.'）。 状态：dp[i][j] = s[:i] 是否被 p[:j] 完全匹配。 时间 O(m*n)，空间 O(m*n)。 """ _validate_basic(p) m, n = len(s), len(p) dp = [[False] * (n + 1) for _ in range(m + 1)] dp[0][0] = True # 空串只能被形如 a*b*c* 的模式匹配：'*' 取零次 for j in range(2, n + 1): if p[j - 1] == "*":...

AI 评审点评

以下是 AI 评审对该模型输出的点评：

【KIMI】该实现是一份高质量的算法工程解答，完整覆盖了题目所有要求：算法思路说明、DP 与回溯的选型论证、复杂度分析、面向对象的两阶段设计、PEP 8 规范代码、全面的异常处理与测试验证。核心 DP 逻辑严谨，`*` 的零次/多次转移处理精准，字符类扩展功能实现正确。整体达到生产代码水准，仅在空间优化未落地、大范围字符类展开策略上有微瑕。

相关链接

您可以通过以下链接查看更多相关内容：

加载中...
100%