最长公共子序列的实现问题

Question

我正在做这个挑战：https://leetcode.com/problems/longest-common-subsequence/

我尝试了多种方法来调试我的代码，但我无法找出问题所在。

就像我脑海中想象的遍历方式一样，从左上角开始

0,0

，值为

0

   o a f c
 d 0 0 0 0 
 a 0 1 1 1
 f 0 1 2 2
 c 0 1 2 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

Answer 1

问题是你的逻辑毫无意义。你甚至根本不应该传递

current

。要了解原因，让我们回到最长公共子序列的定义：

将

lcs(i, j)

定义为字符串

s[i..]

和

t[j..]

的最长公共子序列（即分别从s和t的第i个和第j个字符开始的后缀的LCS）。那么

lcs(0, 0)

就是问题的答案。

我们可以递归地定义

lcs(i, j)

，如下（伪代码）：

lcs(i, j)
  | if i = |s| or j = |t| -> 0
  | if s[i] = s[j] -> 1 + lcs(i + 1, j + 1)
  | otherwise -> max(lcs(i + 1, j), lcs(i, j + 1))

第一条规则说，如果

s[i..]

或

t[j..]

为空，则 LCS 为 0，这是有道理的，因为空字符串不能有任何共同字符。

第二条规则说，如果

s[i..]

和

t[j..]

的第一个字符相等，那么你应该保留那个共享字符（因此是

1 + 

），并继续递归地解决

s[i+1..]

和

t[j+1..]的问题

.

第三条规则说，如果

s[i..]

和

t[j..]

的第一个字符不相等，那么显然您必须删除第一个字符 s 或 t （或者可能两者都删除，但这种情况是递归处理的）。

现在，要在 Swift 中实现此功能，您可以将此逻辑直接转换为您的助手：

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

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

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

这实际上是重要的一步！每当您有一个使用带记忆化的递归的解决方案，并且它无法正常工作时，首先实现不带记忆化的递归解决方案。当您尚未验证递归解决方案是否有效时，您不应该在此处发布使用记忆化的问题。

上面的代码实际上给出了正确的答案！但它的效率非常低下。要解决这个问题，只需添加备忘录而不更改计算逻辑：

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) -> Int {
            guard s.s1 < t1.count && s.s2 < t2.count else {
                return 0
            }
            guard cache[s] == nil else {
                return cache[s]!
            }
            if t1[s.s1] == t2[s.s2] {
                cache[s] = helper(s: Stage(s.s1 + 1, s.s2 + 1)) + 1
            } else {
                cache[s] = max(helper(s: Stage(s.s1 + 1, s.s2)), helper(s: Stage(s.s1, s.s2 + 1)))
            }
            return cache[s]!
        }
        return helper(s: Stage(0, 0))
    }
}