✨ 字符串 DP 三连：最长回文子串、最长公共子序列 & 编辑距离（LeetCode 5 / 1143 / 72）

• 🔁 5. 最长回文子串
• 📏 1143. 最长公共子序列
• ✂️ 72. 编辑距离

1️⃣ 最长回文子串（LeetCode 5）

📌 题目描述

给你一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

🧠 解题思路：动态规划

✅ 状态定义

设 dp[i][j] 表示子串 s[i...j] 是否是回文串。

🔁 状态转移方程

• 如果 s[i] == s[j]：

  • 若 j - i < 3，则 dp[i][j] = true
  • 否则：dp[i][j] = dp[i+1][j-1]
• 否则：dp[i][j] = false

✅ Go 实现

func longestPalindrome(s string) string {
   
    n := len(s)
    if n < 2 {
   
        return s
    }

    dp := make([][]bool, n)
    for i := range dp {
   
        dp[i] = make([]bool, n)
    }

    maxLen := 1
    start := 0

    for r := 1; r < n; r++ {
   
        for l := 0; l < r; l++ {
   
            if s[l] == s[r] {
   
                if r - l < 3 {
   
                    dp[l][r] = true
                } else {
   
                    dp[l][r] = dp[l+1][r-1]
                }
            }
            if dp[l][r] && r - l + 1 > maxLen {
   
                maxLen = r - l + 1
                start = l
            }
        }
    }

    return s[start:start+maxLen]
}

2️⃣ 最长公共子序列（LeetCode 1143）

📌 题目描述

给定两个字符串 text1 和 text2，返回它们的最长公共子序列的长度。

🧠 解题思路：二维 DP

✅ 状态定义

dp[i][j] 表示 text1[0...i-1] 和 text2[0...j-1] 的最长公共子序列长度。

🔁 状态转移

• 如果 text1[i-1] == text2[j-1]，说明当前字符可加入序列：
  dp[i][j] = dp[i-1][j-1] + 1
• 否则：
  dp[i][j] = max(dp[i-1][j], dp[i][j-1])

✅ Go 实现

func longestCommonSubsequence(text1 string, text2 string) int {
   
    m, n := len(text1), 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 {
   
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            }
        }
    }

    return dp[m][n]
}

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

3️⃣ 编辑距离（LeetCode 72）

📌 题目描述

给你两个单词 word1 和 word2，请返回将 word1 转换成 word2 所使用的最少操作数（插入、删除、替换）。

🧠 解题思路：经典 DP 模板题

✅ 状态定义

dp[i][j] 表示将 word1[0...i-1] 转换为 word2[0...j-1] 所需的最小编辑距离。

🔁 状态转移

• 如果 word1[i-1] == word2[j-1]，则 dp[i][j] = dp[i-1][j-1]

• 否则取三种操作的最小值加 1：

  • 插入：dp[i][j-1] + 1
  • 删除：dp[i-1][j] + 1
  • 替换：dp[i-1][j-1] + 1

✅ Go 实现

func minDistance(word1 string, word2 string) int {
   
    m, n := len(word1), len(word2)
    dp := make([][]int, m+1)
    for i := range dp {
   
        dp[i] = make([]int, n+1)
    }

    for i := 0; i <= m; i++ {
   
        dp[i][0] = i
    }
    for j := 0; j <= n; j++ {
   
        dp[0][j] = j
    }

    for i := 1; i <= m; i++ {
   
        for j := 1; j <= n; j++ {
   
            if word1[i-1] == word2[j-1] {
   
                dp[i][j] = dp[i-1][j-1]
            } else {
   
                dp[i][j] = min(
                    dp[i-1][j-1], // 替换
                    dp[i][j-1],   // 插入
                    dp[i-1][j],   // 删除
                ) + 1
            }
        }
    }

    return dp[m][n]
}

func min(a, b, c int) int {
   
    if a < b {
   
        if a < c {
   
            return a
        }
        return c
    }
    if b < c {
   
        return b
    }
    return c
}

✅ 总结对比