二刷 LeetCode：5. 最长回文子串 1143. 最长公共子序列 复盘笔记

目录

一、5. 最长回文子串

题目回顾

思路复盘

方法 1：中心扩展法（最直观、推荐）

方法 2：动态规划（进阶理解）

易错点 & 二刷心得

二、1143. 最长公共子序列

题目回顾

思路复盘

空间优化版（一维 DP）

易错点 & 二刷心得

三、两道题的共性总结 & 二刷收获

这两道题都是动态规划的经典代表，也是面试高频考点，二刷时我们重点拆解思路、优化写法，顺便把易错点和通用模板总结清楚。

一、5. 最长回文子串

题目回顾

给你一个字符串s，找到s中最长的回文子串。回文子串是指正读和反读都相同的字符串，子串是连续的字符序列。

思路复盘

方法 1：中心扩展法（最直观、推荐）

核心思想：回文串是对称的，所以可以以每个字符（或字符间隙）为中心，向两边扩展，找到以该中心为轴的最长回文串。

• 回文串有两种形式：
  1. 奇数长度：中心是一个字符（如aba，中心是b）
  2. 偶数长度：中心是两个字符的间隙（如abba，中心在两个b之间）
• 实现步骤：
  1. 遍历字符串的每个位置i，分别以i（奇数长度）和i+1（偶数长度）为中心扩展
  2. 每次扩展时，判断左右边界的字符是否相等，相等则继续扩展，否则停止
  3. 记录扩展过程中得到的最长回文串的起始和结束位置

Java 代码实现

java

运行

public String longestPalindrome(String s) { if (s == null || s.length() < 1) return ""; int start = 0, end = 0; for (int i = 0; i < s.length(); i++) { int len1 = expandAroundCenter(s, i, i); // 奇数长度 int len2 = expandAroundCenter(s, i, i + 1); // 偶数长度 int len = Math.max(len1, len2); if (len > end - start) { start = i - (len - 1) / 2; end = i + len / 2; } } return s.substring(start, end + 1); } private int expandAroundCenter(String s, int left, int right) { while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) { left--; right++; } return right - left - 1; }

方法 2：动态规划（进阶理解）

核心思想：用dp[i][j]表示s[i..j]是否为回文子串。

• 状态转移方程：
  • 如果s[i] == s[j]且dp[i+1][j-1]为 true，则dp[i][j] = true
  • 边界条件：dp[i][i] = true（单个字符是回文），dp[i][i+1] = (s[i] == s[i+1])（两个字符相等则为回文）
• 遍历顺序：从短到长枚举子串长度，保证计算dp[i][j]时，dp[i+1][j-1]已经计算完成

Java 代码实现

java

运行

public String longestPalindrome(String s) { int n = s.length(); if (n < 2) return s; boolean[][] dp = new boolean[n][n]; int maxLen = 1; int start = 0; // 单个字符都是回文 for (int i = 0; i < n; i++) { dp[i][i] = true; } // 枚举子串长度 for (int len = 2; len <= n; len++) { for (int i = 0; i <= n - len; i++) { int j = i + len - 1; if (s.charAt(i) != s.charAt(j)) { dp[i][j] = false; } else { if (len == 2) { dp[i][j] = true; } else { dp[i][j] = dp[i+1][j-1]; } } if (dp[i][j] && len > maxLen) { maxLen = len; start = i; } } } return s.substring(start, start + maxLen); }

易错点 & 二刷心得

1. 中心扩展的边界处理：expandAroundCenter函数中，退出循环时left和right已经越界，所以长度计算要减 1：right - left - 1。
2. DP 方法的遍历顺序：必须先枚举子串长度，再枚举起点，否则会出现dp[i+1][j-1]未计算的情况。
3. 两种方法的选择：中心扩展法时间复杂度 O (n²)，空间复杂度 O (1)，是面试中最推荐的解法；DP 方法适合理解回文子串的动态规划思路，空间复杂度 O (n²)，可优化到 O (n)。

二、1143. 最长公共子序列

题目回顾

给定两个字符串text1和text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0。子序列是由字符串派生而来的序列，删除（或不删除）字符串中的某些字符而不改变其余元素的顺序。

思路复盘

这是二维动态规划的经典题，核心是定义状态和状态转移方程。

1. 状态定义：dp[i][j]表示text1[0..i-1]和text2[0..j-1]的最长公共子序列长度（为了方便处理边界，i 和 j 从 1 开始）。
2. 状态转移：
   • 如果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])
3. 初始状态：dp[0][j] = 0，dp[i][0] = 0（空字符串和任何字符串的公共子序列长度都是 0）
4. 结果：dp[m][n]，其中m和n分别是text1和text2的长度

Java 代码实现（二维 DP）

java

运行

public int longestCommonSubsequence(String text1, String text2) { int m = text1.length(); int n = text2.length(); int[][] dp = new int[m + 1][n + 1]; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (text1.charAt(i - 1) == text2.charAt(j - 1)) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[m][n]; }

空间优化版（一维 DP）

因为dp[i][j]只依赖dp[i-1][j-1]、dp[i-1][j]和dp[i][j-1]，所以可以用一维数组优化空间复杂度到 O (n)：

java

运行

public int longestCommonSubsequence(String text1, String text2) { int m = text1.length(); int n = text2.length(); int[] dp = new int[n + 1]; for (int i = 1; i <= m; i++) { int prev = 0; // 保存dp[i-1][j-1]的值 for (int j = 1; j <= n; j++) { int temp = dp[j]; if (text1.charAt(i - 1) == text2.charAt(j - 1)) { dp[j] = prev + 1; } else { dp[j] = Math.max(dp[j], dp[j - 1]); } prev = temp; } } return dp[n]; }

易错点 & 二刷心得

1. 状态定义的边界处理：dp[i][j]定义为前i个和前j个字符的公共子序列，这样可以避免处理i=0或j=0时的边界问题。
2. 一维优化的关键：必须用prev变量保存dp[i-1][j-1]的值，否则在更新dp[j]时会覆盖之前的值。
3. 和最长递增子序列的区别：最长递增子序列是单字符串的问题，最长公共子序列是双字符串的问题，两者的 DP 思路有相似之处，但状态定义和转移方程不同。

三、两道题的共性总结 & 二刷收获

1. 动态规划的核心：
   • 明确状态定义：把问题分解成子问题，定义dp[i][j]表示什么
   • 找到状态转移方程：根据当前字符是否相等，推导状态转移的逻辑
2. 优化意识：
   • 最长回文子串：从暴力法到中心扩展法，把时间复杂度从 O (n³) 降到 O (n²)，空间复杂度降到 O (1)
   • 最长公共子序列：从二维 DP 到一维 DP，把空间复杂度从 O (mn) 降到 O (min (m,n))
3. 面试重点：
   • 最长回文子串：中心扩展法是必须掌握的，要能讲清楚两种中心的扩展逻辑
   • 最长公共子序列：二维 DP 的思路是基础，一维优化是加分项，要理解优化的原理