使用LazyList作为缓存以函数式方法求解LeetCode最长回文子串为何出现TLE？

你的思路是想用LazyList做缓存来实现动态规划，但超时的核心问题在于LazyList的计算顺序和动态规划需要的依赖顺序完全不匹配，导致缓存根本没发挥作用，反而触发了大量重复计算。让我一步步拆解问题：

1. 动态规划的依赖顺序搞反了 #

最长回文子串的动态规划逻辑中，判断s[i..j]是否是回文，依赖的是s[i+1..j-1]的结果——也就是更短的、右下角的子问题。正确的计算顺序应该是按子串长度从小到大：先算所有长度为1的子串，再长度2，直到长度n的子串。这样当计算长度l的子串时，长度l-2的子串结果已经存在缓存里了。

但你的LazyList.tabulate(n,n)是按行优先顺序生成元素的：先算i=0的所有j（子串长度从1到n），再算i=1的所有j，以此类推。当你计算mem(0)(5)（长度6的子串）时，需要mem(1)(4)，而mem(1)(4)还没被计算过，于是会触发mem(1)(4)的计算；mem(1)(4)又需要mem(2)(3)，同样没被计算过，继续触发……直到递归到长度1的子串。这就导致每个子问题都被重复计算了多次，时间复杂度从动态规划的O(n²)退化成了指数级的O(2ⁿ)，自然会超时。

2. LazyList的“懒加载”在这里反而帮了倒忙 #

LazyList的设计是用到某个元素时才计算它，但你的依赖链是反向的：先触发了长串的计算，而长串依赖的短串还没被缓存。每次触发计算都会重新走一遍递归逻辑，相当于完全没有利用缓存——因为你需要的子问题结果还没被提前计算并存储下来，每次都要重新推导。

比如当你遍历mem.foreach(_.force)时，按行遍历的顺序会先试图计算mem(0)(0)、mem(0)(1)、mem(0)(2)……计算mem(0)(2)时需要mem(1)(1)，这时候mem(1)(1)才第一次被计算；之后当计算mem(1)(2)时，又需要mem(2)(1)（返回-1），但如果之后有其他子问题需要mem(1)(1)，它已经被缓存了，这部分是对的，但大部分长串的计算都会触发递归到未缓存的短串，导致大量重复计算。

3. 额外的性能开销 #

每次访问mem(i)(j)时，LazyList都要做一次延迟加载的检查（判断这个元素是否已经被计算过），相比直接用数组（O(1)直接访问），这会带来额外的常数开销。对于n较大的输入，这种开销会被放大。

怎么改进？ #

如果你想继续用动态规划，建议改用二维数组，并按子串长度从小到大填充：

object Solution {
  def longestPalindrome(s: String): String = {
    val n = s.length
    if (n == 0) return ""
    // dp(i)(j) 表示 s[i..j] 是否是回文
    val dp = Array.ofDim[Boolean](n, n)
    var start = 0
    var maxLen = 1

    // 长度为1的子串都是回文
    for (i <- 0 until n) {
      dp(i)(i) = true
    }

    // 长度为2的子串
    for (i <- 0 until n - 1) {
      if (s(i) == s(i + 1)) {
        dp(i)(i + 1) = true
        start = i
        maxLen = 2
      }
    }

    // 长度从3到n的子串
    for (len <- 3 to n) {
      for (i <- 0 until n - len + 1) {
        val j = i + len - 1
        if (s(i) == s(j) && dp(i + 1)(j - 1)) {
          dp(i)(j) = true
          start = i
          maxLen = len
        }
      }
    }

    s.slice(start, start + maxLen)
  }
}

如果你坚持想用LazyList，那必须调整它的构建顺序，让子问题按依赖顺序被提前计算。但这种场景下，数组的实现会更直接高效，毕竟动态规划的依赖顺序是明确的，不需要懒加载的特性。

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