如何优化JS字符串拆分校验算法，降低内存占用适配超大型字符串场景

原有实现的问题 #

原有两个版本的实现核心缺陷如下：

• 反复调用replace方法，每次替换都会生成全新的字符串副本，对于千万级长度的超大字符串，多次复制会导致内存占用飙升，远超100MB限制。
• 替换顺序依赖固定的匹配优先级，极端场景下可能出现匹配错误。

优化思路 #

采用滚动动态规划方案，仅需一次遍历字符串，无需修改原字符串，内存开销固定为O(1)，完全满足约束要求：

• 定义dp[i]为前i个字符是否可以被合法拆分
• 状态转移仅依赖前1、3、4位的状态，因此不需要存储完整的dp数组，仅用长度为5的滚动数组即可存储所有需要的状态
• 遍历过程中依次匹配三个合法模式，无需回溯

优化后代码 #

let solution = (password) => {
  const n = password.length;
  if (n === 0) return false;
  // 滚动数组仅存储最近5个状态，内存占用固定
  const dp = new Array(5).fill(false);
  dp[0] = true; // 基准状态：0个字符视为合法起点
  
  for (let i = 1; i <= n; i++) {
    const currIdx = i % 5;
    dp[currIdx] = false;
    
    // 匹配长度为1的模式 "4"
    if (i >= 1 && dp[(i - 1) % 5] && password[i - 1] === '4') {
      dp[currIdx] = true;
    }
    
    // 匹配长度为3的模式 "422"
    if (!dp[currIdx] && i >= 3 && dp[(i - 3) % 5]) {
      if (password[i-3] === '4' && password[i-2] === '2' && password[i-1] === '2') {
        dp[currIdx] = true;
      }
    }
    
    // 匹配长度为4的模式 "2222"
    if (!dp[currIdx] && i >= 4 && dp[(i - 4) % 5]) {
      if (password[i-4] === '2' && password[i-3] === '2' && password[i-2] === '2' && password[i-1] === '2') {
        dp[currIdx] = true;
      }
    }
  }
  
  return dp[n % 5];
}

// 测试用例验证
console.log(solution('4')); // true
console.log(solution('44')); // true
console.log(solution('42')); // false
console.log(solution('4224224')); // true
console.log(solution('42222')); // true
console.log(solution('22224')); // true

方案优势 #

• 内存占用极低：固定使用5个布尔值的数组，无论输入字符串多大，内存开销都可以忽略，远低于100MB限制。
• 执行效率高：仅线性遍历一次字符串，无任何字符串复制、查找操作，千万级长度字符串可在毫秒级完成校验。
• 逻辑严谨：覆盖所有合法匹配场景，不存在匹配顺序导致的错误问题。
• 完全符合约束：没有使用任何正则表达式。

内容的提问来源于stack exchange，提问作者Nick