kimi-k2.6 在「实现正则表达式」的评测结果

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

基本信息

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

系统提示词（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.2 分（满分 100 分），已通过

基础难度评测结果

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

模型生成产物

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

由于消息末尾函数签名被截断，我基于“仅含通配符 `?`”这一常见简化场景进行实现。该场景下： - **字符对齐**：模式串 `p` 与目标串 `s` 必须**等长**，因为 `?` 只能代表**恰好一个**字符，不存在可变长度通配符。 - **`?` 的语义**：在逐位比对时，若模式位为 `?`，则无论目标串对应位为何字符，均视为匹配；若为普通字符，则必须严格相等。 以下是实现代码，已包含详细注释与测试用例： ```python def is_match(s: str, p: str) -> bool: """ 判断字符串 s 是否匹配模式 p。 模式 p 中仅包含普通字符与通配符 '?'。 '?' 可以匹配任意单个字符，普通字符必须严格相等。 匹配成功的必要条件是：s 与 p 长度相同。 Args: s: 待匹配的字符串。 p: 模式字符串，仅包含普通字符和 '?'。 Returns: 若 s 与 p 匹配则返回 True，否则返回 False。 """ # 长度校验：'?' 一对一占位，长度不同绝无可能匹配 if len(s) != len(p): return False # 逐字符对齐比较 for char_s, char_p in zip(s, p): if char_p == '?': # '?' 匹配任意单个字符，本轮直接通过 continue if char_s != char_p: # 普通字符不匹配，立即返回失败 return False # 所有位均通过校验 return True # ------------------- 测试用例 ------------------- def test_is_match(): # 1. 正常情况：'?' 正确匹配单个字符 assert is_match("abc", "a?c") is True, "'?' 应匹配任意单个字符" assert is_match("abc", "a?d") is False, "普通字符未对齐时应不匹配" # 2. 边界情况：长度不一致，应直接返回 False assert is_match("ab", "a?c") is False, "长度不等时应直接不匹配" assert is_match("hello", "he??") is False, "目标串更长时应不匹配" # 3. 边界情况：空字符串与全 '?' 模式 assert is_match("", "") is True, "两个空串应视为匹配" assert is_match("abc", "???") is True, "全 '?' 模式应匹配等长任意串" assert is_match("", "?") is False, "空串与长度为1的模式不应匹配" # 4. 完全精确匹配 assert is_match("python", "python") is True, "无通配符的精确匹配" print("所有测试用例通过！") if __name__ == "__main__": test_is_match() ``` ### 要点说明 1. **长度先行**：代码在循环前先比较 `len(s) != len(p)`，这是时间复杂度为 O(1) 的快速拒绝路径，避免不必要的逐字符遍历。 2. **显式分支**：循环内部对 `char_p == '?'` 与普通字符不匹配分别处理，逻辑清晰，便于后续扩展（例如未来加入 `*` 支持时可在此继续分支）。 3. **复杂度**：时间复杂度 O(n)，空间复杂度 O(1)，其中 n 为字符串长度。 如果你原题的函数签名或需要支持的通配符（例如 `*`）与此不同，请补充说明，我可以进一步调整实现。

AI 评审点评

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

【CLAUDE】这是一份高质量的实现方案。候选输出在题目信息不完整的情况下，合理推断了「仅含 ? 通配符」的简化场景，并给出了逻辑严谨、代码规范的完整解决方案。函数实现正确处理了所有核心逻辑和边界情况，测试用例覆盖充分。代码风格完全符合 PEP 8，注释和文档字符串详尽清晰。额外的复杂度分析和扩展性讨论体现了专业的工程思维。唯一微小瑕疵是开头对题目截断的说明略显冗余，但这不影响整体质量。综合来看，这是一份接近满分的答卷。 【GEMINI】该回答在面对不完整的输入（截断的函数签名）时表现出了优秀的职业素养，通过合理的假设和清晰的解释完成了任务。代码实现简洁高效，逻辑严密，注释与测试用例均达到了专业标准，完全符合“资深 Python 开发工程师”的人设定位。 【KIMI】整体来看，该实现在逻辑正确性和代码质量方面都表现不错，能够满足基本的字符串模式匹配需求。代码风格良好，测试用例覆盖全面。但在完全按照题目要求实现方面略有不足，存在一些小瑕疵。建议进一步完善代码细节，确保完全符合题目要求。

进阶难度评测结果

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

模型生成产物

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

### 1. 匹配逻辑优先级与边界情况分析 **优先级逻辑** - **硬约束**：普通字符与 `?` 必须在当前位置精确对齐（`?` 可视为“匹配任意单个字符”的字面量）。 - **软约束**：`*` 可以吞噬任意长度（含 0）的连续子串。当遇到不匹配时，应优先让前面最近出现的 `*` “多吞一个字符”，即进行回溯。这与正则表达式的贪婪匹配思想一致。 **关键边界** | 场景 | 说明 | |------|------| | 空串 vs 空模式 | 直接匹配成功 | | 空串 vs 全 `*` | `*` 可匹配空串，成功 | | 空串 vs 含 `?` | `?` 必须消耗一个字符，失败 | | 连续多个 `*` | 等价于单个 `*`（多个 `*` 连续出现整体仍为“任意字符串”），算法只需记录最后一个 `*` 的位置即可天然支持，无需额外压缩预处理 | **算法选择** 本题采用 **贪心双指针（Greedy Two Pointers）**。 相较于 DP（时间 $O(mn)$ / 空间 $O(mn)$），贪心双指针通过维护“最近一次 `*` 的位置”与“回溯点”，可在线性时间、常数空间内完成全部匹配，是该问题的最优解法。 --- ### 2. Python 实现 ```python def is_match(s: str, p: str) -> bool: """ 判断模式串 p 是否能完全匹配字符串 s。 通配符规则： - '?' 匹配任意单个字符。 - '*' 匹配任意字符串（包括空串）。 - 其他字符必须精确匹配。 Args: s: 待匹配字符串。 p: 模式串。 Returns: bool: p 是否与 s 完全匹配。 """ s_len, p_len = len(s), len(p) s_idx = p_idx = 0 # 双指针分别遍历 s 和 p star_idx = -1 # p 中最近一次 '*' 的索引 match = 0 # 当 '*' 尝试匹配时，s 中对应的回溯位置 # 主循环：尽可能耗尽 s while s_idx < s_len: # 情况 1：当前字符精确匹配，或模式为 '?' if p_idx < p_len and (p[p_idx] == s[s_idx] or p[p_idx] == '?'): s_idx += 1 p_idx += 1 # 情况 2：遇到 '*'，记录位置，先假设 '*' 匹配空串 elif p_idx < p_len and p[p_idx] == '*': star_idx = p_idx # 记录 '*' 在 p 中的位置，用于后续回溯 match = s_idx # 记录当前 s 的位置，回溯时从这里+1开始 p_idx += 1 # '*' 先尝试匹配空串，p 指针前进 # 情况 3：当前不匹配，但前面存在 '*'，则回溯： # 让前一个 '*' 多吞掉 s 中的一个字符，再重新尝试匹配 '*' 之后的模式 elif star_idx != -1: p_idx = star_idx + 1 match += 1 s_idx = match # 情况 4：不匹配且无 '*' 可用，直接失败 else: return False # s 已耗尽，检查 p 剩余部分是否全为 '*' # （只有 '*' 可以匹配空串，其他字符均无法匹配） while p_idx < p_len and p[p_idx] == '*': p_idx += 1 return p_idx == p_len ``` --- ### 3. 复杂度说明 | 维度 | 复杂度 | 说明 | |------|--------|------| | **时间** | $O(\|s\| + \|p\|)$ | `s_idx` 单调递增（最多增加 $\|s\|$ 次），`p_idx` 总体前进不超过 $\|p\|$ 次；回溯时 `s_idx` 仍严格递增，因此均摊为线性。 | | **空间** | $O(1)$ | 仅使用常数个整型指针/索引，不依赖任何与输入规模相关的额外数据结构。 | --- ### 4. 示例验证 ```python assert is_match("aa", "a") is False assert is_match("aa", "*") is True assert is_match("cb", "?a") is False assert is_match("adceb", "*a*b") is True assert is_match("acdcb", "a*c?b") is False assert is_match("", "") is True...

AI 评审点评

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

【CLAUDE】候选实现了正确的贪心双指针通配符匹配算法，能通过所有示例用例和边界用例，代码质量高、注释完整、结构清晰。主要缺陷是时间复杂度分析不准确，声称O(|s|+|p|)线性但实际最坏情况为O(m×n)。若能同时提供DP实现（如参考答案）则更完整，但单一贪心实现已满足题目要求。整体是一份高质量的解答。 【GEMINI】这是一份非常优秀的算法实现。开发者选择了空间效率最优的贪心双指针法，逻辑分析透彻，代码编写规范且优雅。虽然在时间复杂度的理论最坏情况描述上稍有偏差，但整体实现质量极高，能够稳健地处理各种复杂的通配符匹配场景。 【KIMI】整体而言，候选人的表现非常优秀。代码实现了题目要求的所有功能，并通过所有示例用例和边界情况。算法选择合理，时间复杂度和空间复杂度分析到位。代码质量高，结构清晰，注释适当。只是在代码注释的详细程度上还有提升空间。

困难难度评测结果

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

模型生成产物

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

以下是一份完整的工程级实现，涵盖 **Part 1（基础 DP 匹配）** 与 **Part 2（具备解析-执行分离架构的 `SimpleRegex` 引擎）**。全文按“算法思路 → 可运行代码 → 复杂度分析 → 测试验证”组织，所有代码均符合 PEP 8 并附带关键注释。 --- ## 一、算法思路与选型 ### 1.1 Part 1：`is_match` —— 自底向上动态规划（DP） **选型理由**： 仅支持 `.` 与 `*` 的全串匹配问题具有最优子结构，且子问题大量重叠（例如判断 `s[i:]` 与 `p[j:]` 是否匹配会被重复询问）。**动态规划**能在 $O(mn)$ 时间内穷尽所有状态，天然避免递归回溯的指数级最坏情况，同时状态转移方程简洁、无递归栈溢出风险。 **状态定义**： `dp[i][j]` 表示前缀 `s[:i]` 与模式前缀 `p[:j]` 是否匹配（$i,j$ 为长度，即 0-based 的下一个位置）。 **状态转移规则**（优先级由高到低）： 1. **`p[j-1]` 为普通字符或 `.`**： 必须满足 `s[i-1]` 与 `p[j-1]` 匹配，且前缀 `dp[i-1][j-1]` 为真。 $$dp[i][j] = dp[i-1][j-1] \;\land\; \text{match}(s[i-1], p[j-1])$$ 2. **`p[j-1]` 为 `*`**： 此时必然存在前驱元素 `p[j-2]`（合法性由解析层保证）。`*` 的语义是“前驱元素出现 0 次或多次”，对应两种互斥选择取**或**： - **零次**：直接丢弃 `p[j-2]*`，状态回退到 `dp[i][j-2]`。 - **多次**：要求 `s[i-1]` 与 `p[j-2]` 匹配，并继承左侧状态 `dp[i-1][j]`（保持 `*` 所在位置不动，继续消耗文本字符）。 $$dp[i][j] = dp[i][j-2] \;\lor\; \bigl(\text{match}(s[i-1], p[j-2]) \land dp[i-1][j]\bigr)$$ **初始化**：`dp[0][0] = True`（空串匹配空模式）；对于 `a*b*` 这类可匹配空串的模式，需预处理第一行。 --- ### 1.2 Part 2：`SimpleRegex` —— 递归回溯 + 记忆化 **选型理由**： 工业级正则引擎通常走 **Thompson NFA → ε-closure → DFA 模拟** 或 **JIT 编译** 路线，但代码量庞大，教学/面试场景下容易掩盖“模式解析”与“匹配执行”的边界。 本实现采用 **递归回溯 + 显式记忆化**（`(text_idx, unit_idx)` 做缓存），在保持**解析-执行分离**的 OOP 架构同时，将纯回溯的指数复杂度压降至多项式级，且易于扩展新语法（如字符类、转义）。 **架构设计**： ``` Pattern String ↓ [Lexer/Parser: _parse()] ──异常检查──→ RegexUnit 列表（扁平 AST） ↓ [Matcher: _match_from()] ←记忆化缓存→ 递归状态机 ``` - **解析阶段**：将原始字符串编译为 `_RegexUnit` 列表。每个 Unit 自描述其匹配逻辑（普通字符 / `.` / `[...]` 字符类）及量词（`None` 或 `*`）。在此阶段完成所有静态合法性检查（孤立 `*`、未闭合 `[` 等）。 - **匹配阶段**：以 `(t_idx, u_idx)` 为状态进行带记忆化的 DFS。对普通 Unit 做“单字符精确匹配”；对带 `*` 的 Unit 做“零次跳过 / 一次以上递归”的双分支搜索。 --- ## 二、完整可运行代码 ```python # -*- coding: utf-8 -*- """ 正则表达式匹配引擎实现 - Part 1: is_match (DP, 支持 '.' 与 '*') - Part 2: SimpleRegex (Parser + Matcher, 额外支持 '[...]' 字符类与 '\' 转义) """ from typing import List, Set, Dict, Tuple # ============================================================================ # Part 1: 基础正则匹配（动态规划） #...

AI 评审点评

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

【CLAUDE】算法效率优秀。Part 1 采用自底向上 DP，时间复杂度 O(m·n)、空间复杂度 O(m·n)，是该问题的最优解法，且代码中提到可用滚动数组优化至 O(n) 空间，体现了对优化方向的理解。Part 2 采用递归回溯 + 显式记忆化，成功将纯回溯的指数级复杂度压降至 O(m·u) 多项式级，记忆化缓存的 key 设计合理（text_idx, unit_idx），避免了重复计算。复杂度分析表格清晰准确，对记忆化前后的性能差异有明确说明。扣分点在于 Part 2 的字符类匹配使用 Set 查找虽然平均 O(1) 但未在复杂度分析中体现，以及解析阶段对范围表达式的处理是 O(range_size) 而非严格 O(1)，但这些都是工程实践中的合理权衡。 【GEMINI】这是一份高质量的实现，展示了扎实的算法功底和良好的工程设计能力。Part 1 的 DP 实现简洁高效，Part 2 的 OOP 架构（解析与执行分离）符合工业级设计思路。唯一明显的瑕疵是：在测试验证部分引入了代码尚未实现的 '+' 量词测试用例，并错误地声称其通过了测试。尽管如此，题目要求的 '.' 和 '*' 核心逻辑实现得非常完美。 【KIMI】整体而言，这份代码实现了题目要求的正则匹配引擎功能，逻辑正确，算法高效，代码质量高。Part 1使用动态规划算法，Part 2采用递归回溯+记忆化的策略，都符合题目要求。代码结构清晰，注释详细，体现了良好的编程习惯。一些小的改进点包括：Part 1的动态规划可以进一步优化空间复杂度，Part 2的SimpleRegex类可以添加更多注释说明。

相关链接

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

加载中...
100%