最长公共子序列（LCS）实现异常问题排查求助

我正在做LeetCode的最长公共子序列题目，尝试了多种调试方法仍无法定位代码问题。我预期的遍历过程对应的动态规划表如下：

o a f c
 d 0 0 0 0 
 a 0 1 1 1
 f 0 1 2 2
 c 0 1 2 3

但我的Swift代码运行时部分测试用例失败，比如调用longestCommonSubsequence("oafc", "dafc")返回1，而非预期的3。以下是我的实现代码及测试断言：

class Solution {
    func longestCommonSubsequence(_ text1: String, _ text2: String) -> Int {
        var t1: [Character] = Array(text1)
        var t2: [Character] = Array(text2)

        var cache: [Stage: Int] = [:]

        func helper(s: Stage, current: Int) ->  Int { 
            guard s.s1 < t1.count && s.s2 < t2.count else {            
                return current
            }
        
            guard cache[s] == nil else {
                return cache[s]!
            }

            if t1[s.s1] == t2[s.s2] {
                let stage = Stage(s.s1 + 1, s.s2 + 1)
                cache[s] = helper(s: stage, current: current + 1)
                return cache[s]!                 

            } else {
                let stage1 = Stage(s.s1, s.s2 + 1)
                cache[stage1] = helper(s: stage1, current: current)
                let stage2 = Stage(s.s1 + 1, s.s2)
                cache[stage2] = helper(s: stage2, current: current)
                cache[s] = max(cache[stage1]!, cache[stage2]!, current) 

                return cache[s]!
            }
        }
        helper(s: Stage(0,0), current: 0)

        return cache.map{$1}.max()!
    }
}

struct Stage: Hashable {
    var s1: Int
    var s2: Int
    
    init(_ s1: Int, _ s2: Int) {
        self.s1 = s1
        self.s2 = s2
    }
}

let s = Solution()
assert(s.longestCommonSubsequence("ae", "be") == 1)
assert(s.longestCommonSubsequence("fabc", "dafc") == 2)
assert(s.longestCommonSubsequence("abc", "dafc") == 2)
assert(s.longestCommonSubsequence("afc", "dafc") == 3)
assert(s.longestCommonSubsequence("oafc", "dafc") == 3) // FAILURE: it's equal to 1

问题分析与修复 #

你的代码核心问题有两个：

1. 递归逻辑中current参数的传递错误
   你通过current传递累计长度的方式，会让缓存的Stage值和实际最长子序列长度脱节。正确的递归逻辑应该是：当前Stage的结果由后续递归推导，而非依赖传入的累计值。

2. 返回值逻辑错误
   你最后取缓存中所有值的最大值，但实际上起始Stage(0,0)对应的缓存值就是整个问题的答案，无需遍历所有缓存项。

修复后的代码 #

class Solution {
    func longestCommonSubsequence(_ text1: String, _ text2: String) -> Int {
        let t1 = Array(text1)
        let t2 = Array(text2)
        var cache: [Stage: Int] = [:]

        func helper(s: Stage) -> Int {
            guard s.s1 < t1.count, s.s2 < t2.count else {
                return 0
            }
            if let cached = cache[s] {
                return cached
            }

            let result: Int
            if t1[s.s1] == t2[s.s2] {
                result = 1 + helper(s: Stage(s.s1 + 1, s.s2 + 1))
            } else {
                let option1 = helper(s: Stage(s.s1, s.s2 + 1))
                let option2 = helper(s: Stage(s.s1 + 1, s.s2))
                result = max(option1, option2)
            }
            cache[s] = result
            return result
        }

        return helper(s: Stage(0, 0))
    }
}

struct Stage: Hashable {
    var s1: Int
    var s2: Int
    init(_ s1: Int, _ s2: Int) {
        self.s1 = s1
        self.s2 = s2
    }
}

// 测试断言
let s = Solution()
assert(s.longestCommonSubsequence("ae", "be") == 1)
assert(s.longestCommonSubsequence("fabc", "dafc") == 2)
assert(s.longestCommonSubsequence("abc", "dafc") == 2)
assert(s.longestCommonSubsequence("afc", "dafc") == 3)
assert(s.longestCommonSubsequence("oafc", "dafc") == 3) // 现在通过

修复说明 #

• 移除current参数，递归函数直接返回当前Stage对应的最长公共子序列长度：字符匹配时返回1 + 后续Stage结果，不匹配时返回两个分支的最大值。
• 直接返回helper(s: Stage(0,0))的结果，这就是最终答案，无需遍历缓存。
• 简化缓存读取逻辑，让代码更简洁直观。

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