最长公共子序列问题的核心是通过动态规划计算两个字符串的最长公共子序列长度，再通过回溯从状态表中还原出具体的子序列内容。Go语言作为静态类型语言，在实现过程中需要注意数组索引、循环逻辑和递归回溯的配合，才能保证最终结果的正确性。
LCS动态规划状态定义
首先我们需要明确动态规划的状态定义，假设两个输入字符串分别为text1和text2，长度分别为m和n。我们定义二维数组dp，其中dp[i][j]表示text1的前i个字符和text2的前j个字符的最长公共子序列长度。状态转移规则如下：
- 如果
text1[i-1] == text2[j-1]，说明当前字符属于公共子序列，dp[i][j] = dp[i-1][j-1] + 1 - 如果
text1[i-1] != text2[j-1]，则dp[i][j] = max(dp[i-1][j], dp[i][j-1])
初始化时dp[0][*]和dp[*][0]都为0，表示空字符串和任意字符串的公共子序列长度为0。
Go语言实现LCS长度计算
首先实现计算dp状态表的函数，代码如下：
package main
import "fmt"
// 计算LCS的dp状态表
func computeLCSDP(text1, text2 string) [][]int {
m := len(text1)
n := len(text2)
// 初始化二维dp数组
dp := make([][]int, m+1)
for i := range dp {
dp[i] = make([]int, n+1)
}
// 填充dp数组
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
if text1[i-1] == text2[j-1] {
dp[i][j] = dp[i-1][j-1] + 1
} else {
if dp[i-1][j] > dp[i][j-1] {
dp[i][j] = dp[i-1][j]
} else {
dp[i][j] = dp[i][j-1]
}
}
}
}
return dp
}
LCS回溯的核心逻辑
回溯的过程是从dp[m][n]的位置开始，反向遍历状态表，根据状态转移的规则还原子序列：
- 如果当前
i和j都大于0，且text1[i-1] == text2[j-1]，说明该字符属于公共子序列，将其加入结果，然后同时向i-1、j-1移动 - 如果字符不相等，则向
dp[i-1][j]和dp[i][j-1]中值更大的方向移动，如果两者相等可以任选一个方向 - 当
i或j为0时，回溯结束
需要注意的是，回溯得到的子序列是逆序的，最后需要反转结果得到正确的顺序。
完整回溯实现代码
结合回溯逻辑，完整的Go语言实现代码如下：
package main
import (
"fmt"
"strings"
)
// 计算LCS的dp状态表
func computeLCSDP(text1, text2 string) [][]int {
m := len(text1)
n := len(text2)
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 text1[i-1] == text2[j-1] {
dp[i][j] = dp[i-1][j-1] + 1
} else {
if dp[i-1][j] > dp[i][j-1] {
dp[i][j] = dp[i-1][j]
} else {
dp[i][j] = dp[i][j-1]
}
}
}
}
return dp
}
// 回溯获取LCS具体子序列
func backtrackLCS(text1, text2 string, dp [][]int) string {
m := len(text1)
n := len(text2)
i := m
j := n
var sb strings.Builder
// 回溯收集逆序的子序列字符
for i > 0 && j > 0 {
if text1[i-1] == text2[j-1] {
sb.WriteByte(text1[i-1])
i--
j--
} else {
if dp[i-1][j] > dp[i][j-1] {
i--
} else {
j--
}
}
}
// 反转得到正确顺序的子序列
res := []byte(sb.String())
for left, right := 0, len(res)-1; left < right; left, right = left+1, right-1 {
res[left], res[right] = res[right], res[left]
}
return string(res)
}
func main() {
text1 := "abcde"
text2 := "ace"
dp := computeLCSDP(text1, text2)
lcs := backtrackLCS(text1, text2, dp)
fmt.Printf("字符串1: %sn", text1)
fmt.Printf("字符串2: %sn", text2)
fmt.Printf("最长公共子序列: %sn", lcs)
fmt.Printf("LCS长度: %dn", dp[len(text1)][len(text2)])
}
常见错误与注意事项
在实现LCS回溯时，开发者常出现以下错误：
- 回溯时没有判断
i和j的下界，导致数组越界 - 字符相等时只移动一个指针，导致子序列不完整
- 忘记反转回溯得到的逆序结果，导致子序列顺序错误
- dp数组初始化时长度少加1，导致状态索引对应错误
通过上面的代码实现和逻辑梳理，可以规避这些常见问题，正确实现LCS的回溯过程。