Go语言实现最长公共子序列（LCS）回溯：深度解析与正确实践

本教程深入探讨go语言中最长公共子序列（lcs）的回溯算法实现，重点解决在动态规划表格与字符串索引之间常见的偏移问题。文章详细分析了索引不匹配导致的问题，并提供了一个经过修正的go语言回溯函数，确保lcs能够被正确地重构。通过完整的代码示例和注意事项，帮助读者掌握lcs回溯的正确实践。

引言：最长公共子序列与回溯

最长公共子序列（Longest Common Subsequence, LCS）是计算机科学中一个经典的动态规划问题。给定两个序列，LCS的目标是找到一个最长的序列，该序列是这两个给定序列的子序列。LCS的长度计算通常通过构建一个二维动态规划（DP）表格来完成。然而，仅仅计算出LCS的长度是不够的，在许多实际应用中，我们还需要找出具体的LCS序列本身。这就需要用到“回溯”技术，即根据DP表格中的值逆向追踪，从而重构出LCS。

在Go语言中实现LCS回溯时，一个常见的陷阱是处理DP表格索引与原始字符串索引之间的对应关系。如果处理不当，可能导致回溯结果不完整或错误。本教程将详细解析这一问题，并提供一个健壮且正确的Go语言回溯实现。

LCS长度计算的动态规划基础

在深入回溯之前，我们首先回顾LCS长度的动态规划计算。假设我们有两个字符串 str1 和 str2，长度分别为 m 和 n。我们通常会构建一个 (m+1) x (n+1) 的二维表格 dp。其中，dp[i][j] 表示 str1 的前 i 个字符与 str2 的前 j 个字符的最长公共子序列的长度。

表格填充规则如下：

立即学习“go语言免费学习笔记（深入）”；

1. 初始化: dp[0][j] = 0 和 dp[i][0] = 0，表示空字符串与任何字符串的LCS长度为0。
2. 递推:
   • 如果 str1[i-1] == str2[j-1] (注意这里是字符串的0-based索引，对应DP表格的1-based索引)，则 dp[i][j] = 1 + dp[i-1][j-1]。
   • 如果 str1[i-1] != str2[j-1]，则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

最终，dp[m][n] 将包含 str1 和 str2 的LCS长度。

以下是一个Go语言实现LCS长度计算的示例：

func LCSLength(str1, str2 string) [][]int {
    m := len(str1)
    n := len(str2)

    // dp table is (m+1) x (n+1)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if str1[i-1] == str2[j-1] {
                dp[i][j] = 1 + dp[i-1][j-1]
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            }
        }
    }
    return dp
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

LCS回溯算法原理与常见陷阱

回溯LCS序列的核心思想是从DP表格的右下角（dp[m][n]）开始，逆向追踪路径。

1. 匹配字符: 如果 str1[i-1] == str2[j-1]，这意味着当前字符是LCS的一部分。我们将 str1[i-1]（或 str2[j-1]）添加到LCS序列中，并向左上方移动 (i-1, j-1)。
2. 不匹配字符: 如果 str1[i-1] != str2[j-1]，这意味着当前字符不是LCS的一部分。我们需要查看 dp[i-1][j] 和 dp[i][j-1] 的值，选择其中较大的那个方向移动。
   • 如果 dp[i-1][j] > dp[i][j-1]，则向上移动 (i-1, j)。
   • 如果 dp[i][j-1] >= dp[i-1][j]，则向左移动 (i, j-1)。
3. 终止条件: 当 i 或 j 达到0时，回溯结束。

常见陷阱：索引偏移问题

序列猴子开放平台

具有长序列、多模态、单模型、大数据等特点的超大规模语言模型

0

查看详情

问题通常出现在 Back 函数中对字符串和DP表格索引的混淆。DP表格是 (m+1) x (n+1) 大小的，其索引 i 和 j 通常代表 str1 的前 i 个字符和 str2 的前 j 个字符。这意味着 dp[i][j] 对应的是 str1[0...i-1] 和 str2[0...j-1]。

如果回溯函数 Back(table, str1, str2, i, j) 中的 i 和 j 被设计为直接代表字符串的0-based索引（即 str1[i] 和 str2[j]），那么在访问DP表格时就需要进行调整。

原始代码的错误在于：

• 它将 i 和 j 视为字符串的0-based索引，因此 str1[i] 和 str2[j] 是合法的。
• 然而，它的基本情况 if i == 0 || j == 0 却将 0 视为字符串的起始边界，导致 str1[0] 和 str2[0] 可能被跳过。正确的字符串0-based索引的终止条件应该是 i == -1 || j == -1。
• 在不匹配的情况下，它使用了 table[i][j-1] 和 table[i-1][j]。如果 i 和 j 是字符串索引，那么对应的DP表格索引应该是 i+1 和 j+1。因此，要比较 str1 移除 str1[i] 后与 str2 的LCS长度（对应 table[i][j+1]）和 str2 移除 str2[j] 后与 str1 的LCS长度（对应 table[i+1][j]），而不是 table[i][j-1] 和 table[i-1][j]。

正确的Go语言回溯实现

为了解决上述索引偏移问题，我们需要确保 Back 函数中的 i 和 j 始终表示字符串的0-based索引，并在访问DP表格时进行相应的调整。

以下是修正后的 Back 函数实现：

// Back 函数用于从LCS长度DP表格中回溯出最长公共子序列
// table: 预先计算好的LCS长度DP表格 (m+1)x(n+1)
// str1, str2: 原始字符串
// i, j: 当前回溯点在字符串中的0-based索引
func Back(table [][]int, str1, str2 string, i, j int) string {
    // 基本情况：当任一字符串索引小于0时，表示已遍历完该字符串，返回空字符串
    if i == -1 || j == -1 {
        return ""
    }

    // 如果当前字符匹配 (str1[i] == str2[j])
    // 那么这个字符是LCS的一部分，将其添加到结果中，并向左上方移动 (i-1, j-1)
    if str1[i] == str2[j] {
        return Back(table, str1, str2, i-1, j-1) + string(str1[i])
    } else {
        // 如果当前字符不匹配
        // 比较移除 str1[i] 后的LCS长度 (table[i][j+1])
        // 和移除 str2[j] 后的LCS长度 (table[i+1][j])
        // 注意：table的索引比字符串索引大1
        // table[i][j+1] 对应 str1[:i] 和 str2[:j+1] 的LCS长度
        // table[i+1][j] 对应 str1[:i+1] 和 str2[:j] 的LCS长度
        if table[i+1][j] > table[i][j+1] {
            // 如果移除 str2[j] 后的LCS更长，则向左移动 (即在str2中向前移动，j-1)
            return Back(table, str1, str2, i, j-1)
        } else {
            // 否则（移除 str1[i] 后的LCS更长或相等），则向上移动 (即在str1中向前移动，i-1)
            return Back(table, str1, str2, i-1, j)
        }
    }
}

代码解释：

1. i == -1 || j == -1: 这是正确的字符串0-based索引的终止条件。当 i 或 j 变为 -1 时，意味着我们已经处理了 str1 或 str2 的所有字符。
2. str1[i] == str2[j]: 当字符匹配时，我们将 str1[i] 加入结果，并递归调用 Back(table, str1, str2, i-1, j-1)。这里的 i 和 j 仍然是字符串索引。
3. table[i+1][j] > table[i][j+1]: 这是关键的修正点。
   • i 和 j 是字符串的0-based索引。
   • table[x][y] 存储的是 str1 的前 x 个字符和 str2 的前 y 个字符的LCS长度。
   • 当比较 str1[i] 和 str2[j] 不匹配时，我们需要看：
     • 忽略 str1[i]：LCS长度为 str1 的前 i 个字符与 str2 的前 j+1 个字符的LCS长度，这对应 table[i][j+1]。
     • 忽略 str2[j]：LCS长度为 str1 的前 i+1 个字符与 str2 的前 j 个字符的LCS长度，这对应 table[i+1][j]。
   • 因此，比较 table[i+1][j] 和 table[i][j+1] 是正确的。如果 table[i+1][j] 更大，说明不包含 str2[j] 的路径产生了更长的LCS，所以我们递归调用 Back(table, str1, str2, i, j-1)（在 str2 中向前移动）。反之，则递归调用 Back(table, str1, str2, i-1, j)（在 str1 中向前移动）。

完整示例代码

为了演示如何使用 LCSLength 和 Back 函数，我们提供一个完整的示例：

package main

import (
    "fmt"
    "strings"
)

// max returns the maximum of two integers.
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

// LCSLength computes the length of the Longest Common Subsequence
// and returns the DP table.
func LCSLength(str1, str2 string) [][]int {
    m := len(str1)
    n := len(str2)

    // dp table is (m+1) x (n+1)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if str1[i-1] == str2[j-1] {
                dp[i][j] = 1 + dp[i-1][j-1]
            } else {

以上就是Go语言实现最长公共子序列（LCS）回溯：深度解析与正确实践的详细内容，更多请关注php中文网其它相关文章！