JavaScript 正则表达式匹配子序列的性能优化实践-js教程-PHP中文网

JavaScript 正则表达式匹配子序列的性能优化实践

本文介绍如何通过重构正则模式（用 [^c]*c 替代 w*c）显著提升子序列判断的正则实现性能，避免灾难性回溯，并补充字符转义等生产级注意事项。

本文介绍如何通过重构正则模式（用 `[^c]*c` 替代 `w*c`）显著提升子序列判断的正则实现性能，避免灾难性回溯，并补充字符转义等生产级注意事项。

在使用正则表达式判断字符串 s 是否为 t 的子序列时，直观思路是将 s 转换为“允许任意跳过字符”的模式，例如 "abc" → /w*aw*bw*cw*/。但该写法存在严重性能缺陷：w* 是贪婪且无约束的量词，在匹配失败时会触发深度回溯（backtracking），尤其当 s 较长、t 极长且不匹配时，时间复杂度可能退化至指数级——这正是原代码在 LeetCode 大输入下超时的根本原因。

更优解是精确控制跳过逻辑：对 s 中每个字符 c，只允许匹配 c 之前出现任意个非 c 的字符，即使用 [^c]*c 模式。这样既保证了 c 必须按序出现，又彻底消除了因 w* 匹配重叠导致的无效回溯路径。

以下是优化后的实现：

Java注释规范Skills

当用户要求为 Java 代码添加注释、修改注释、审查注释、整理注释格式，或要求按照代码注释规范处理 Java 文件时，使用本技能。本技能用于统一生成和维护 Java 类注释模板、按 Git 对比 release 判断版本号、补充每行代码上方中文块注释、调整注释空行规则，并保持 Java 文件 UTF-8 无 BOM 编码。典型触发场景包括：补充类注释、更新 @version、检查 @author 来源、整理行尾注释、把注释放到代码上一行、检查注释是否符合规范、构建前检查 Java 注释风格。

下载

/**
 * 判断 s 是否为 t 的子序列（正则优化版）
 * @param {string} s 子序列候选字符串
 * @param {string} t 原字符串
 * @return {boolean}
 */
var isSubsequence = function (s, t) {
    // 提前剪枝：长度不满足直接返回
    if (s.length === 0) return true;
    if (s.length > t.length) return false;

    // 构建正则：对 s 中每个字符 c，生成 `[^c]*c`
    let pattern = '';
    for (let i = 0; i <p><strong>关键优化点说明：</strong>  </p>

✅ 消除回溯源：[^c]* 是原子性匹配（non-backtracking），不会与后续 c 发生冲突；而 w* 可能先吞掉本该属于下一个 c 的字符，导致反复尝试。
✅ 字符转义：使用 c.replace(/[-[]{}()*+?.,\^$|#s]/g, '\$&') 安全转义正则元字符，防止 s 中含 .、* 等时产生意外行为。
✅ 健壮性增强：添加 try/catch 捕获正则编译异常（如超长 pattern 或非法字符），并自动降级至 O(n+m) 的双指针方案。