《字符串相亲记：如何在 O(n²) 内找到你的“完美镜像“？》

《字符串相亲记如何在 O(n²) 内找到你的完美镜像》又名最长回文子序列——一个让字符串自我欣赏的算法一、引子当字符串开始自恋话说在字符串王国里每个字符串都有一个终极梦想——成为回文。什么叫回文就是那种正着读、反着读都一样的字符串比如level、noon、上海自来水来自海上中文乱入。但不是每个字符串都能天生丽质。比如bbbab这个倒霉蛋它想当回文但中间那个a像个电灯泡一样杵在那里破坏了整体的和谐感。于是它想能不能删几个字符让我变成一个回文这就是我们今天的主角——最长回文子序列Longest Palindromic Subsequence。二、什么是子序列别急先吃个汉堡在讲算法之前必须先搞清楚一个概念子序列。假设你有一个汉堡配料依次是[面包, 生菜, 牛肉, 番茄, 面包]。子序列的意思是你可以不吃某些配料但剩下配料的顺序不能变。比如你可以吃[面包, 牛肉, 面包]中间的生菜和番茄扔了这算一个子序列。但你不能变成[牛肉, 面包, 生菜]因为顺序乱了——这就不是子序列而是打乱顺序的黑暗料理了。回到bbbab它的子序列有bbb删掉最后一个a和最后一个bbbbb删掉那个碍眼的abab精简约会版其中最长的回文子序列就是bbbb长度为 4。三、解法一二维 DP——填格子的艺术3.1 核心思想区间 DP我们定义dp[i][j]为字符串s[i...j]这个区间内的最长回文子序列长度。注意这里的关键是区间。我们要解决一个大问题整个字符串先解决一堆小问题所有小区间然后用小问题的答案拼出大问题的答案。3.2 状态转移相爱相杀的两种命运现在我们盯着区间s[i...j]的两端命运 A两端的字符一见钟情s[i] s[j]比如s bbbab区间[0, 4]两端都是b。那太好了这两个b可以手拉手加入回文队伍。此时dp[i][j] dp[i1][j-1] 2意思是中间部分[i1, j-1]能凑出多长的回文再加上我们俩这 2 个字符。命运 B两端的字符相看两厌s[i] ! s[j]比如区间[0, 3]两端是b和a不匹配。那怎么办只能二选一要么去掉左边的b看[1, 3]能搞多长要么去掉右边的a看[0, 2]能搞多长取两者最大值dp[i][j] max(dp[i1][j], dp[i][j-1])3.3 代码登场classSolution{publicintlongestPalindromeSubseq(Strings){intns.length();int[][]dpnewint[n][n];// 对角线初始化单个字符本身就是回文长度为1for(inti0;in;i)dp[i][i]1;// i 从下到上遍历为什么因为 dp[i][j] 依赖 dp[i1][...]for(intin-1;i0;i--){for(intji1;jn;j){if(s.charAt(i)s.charAt(j)){dp[i][j]dp[i1][j-1]2;}else{dp[i][j]Math.max(dp[i1][j],dp[i][j-1]);}}}returndp[0][n-1];}}3.4 填表过程可视化以bbbab为例填完表长这样0(b) 1(b) 2(b) 3(a) 4(b) 0 [ 1 2 3 3 4 ] 1 [ - 1 2 2 3 ] 2 [ - - 1 1 3 ] 3 [ - - - 1 1 ] 4 [ - - - - 1 ]右上角dp[0][4] 4就是答案。复杂度时间 O(n²)空间 O(n²)。优点是思路清晰缺点是空间有点大——就像你租房租了个三居室其实一个人睡就够了。四、解法二一维 DP——断舍离的空间优化面试官看完后点点头“能不能优化一下空间”你微微一笑“可以用滚动数组。”4.1 核心观察仔细看二维 DP 的状态转移dp[i][j]只依赖于dp[i1][j-1]左下角dp[i1][j]正下方dp[i][j-1]左边也就是说第i行只依赖于第i1行。那干嘛存整个二维数组用一维数组就够了4.2 变量们的变形记我们用dp[j]表示当前正在计算的第i行。但问题来了当我们更新dp[j]时需要用到dp[j]的旧值表示dp[i1][j]dp[j-1]的新值表示dp[i][j-1]刚刚算好的dp[i1][j-1]左下角这个最棘手前两个直接用数组就行但左下角怎么办用prev变量来保存classSolution{publicintlongestPalindromeSubseq(Strings){intns.length();int[]dpnewint[n];for(intin-1;i0;i--){dp[i]1;// 对角线初始化intprev0;// 保存 dp[i1][j-1]for(intji1;jn;j){inttempdp[j];// 先保存 dp[i1][j] 的旧值if(s.charAt(i)s.charAt(j)){dp[j]prev2;}else{dp[j]Math.max(dp[j],dp[j-1]);}prevtemp;// 下一轮dp[i1][j] 就变成 dp[i1][j-1] 了}}returndp[n-1];}}4.3 三步走战略temp dp[j]保存旧值dp[i1][j]计算dp[j]的新值dp[i][j]prev temp把旧值交给prev下一轮它就是左下角了这就像接力赛跑prev是接力棒一棒接一棒传下去。复杂度时间 O(n²)空间 O(n)。从三居室搬到单间生活照样精彩。五、解法三LCS 转化——“打不过就搬救兵”面试官推了推眼镜“还有别的思路吗”你胸有成竹“有转化为最长公共子序列问题。”5.1 一个神奇的等式最长回文子序列 原串 与 反转串 的最长公共子序列为什么因为回文串正读反读都一样。如果一个序列是回文那它在原串中是这样在反转串中也是这样——它就是两串的公共子序列比如bbbab反转后是babbb它们的公共子序列bbbb长度为 4。5.2 LCS 的状态转移定义dp[i][j]s[0..i-1]和t[0..j-1]的最长公共子序列长度。if(s[i-1]t[j-1])dp[i][j]dp[i-1][j-1]1;// 相等一起选elsedp[i][j]max(dp[i-1][j],dp[i][j-1]);// 不等二选一5.3 完整代码classSolution{publicintlongestPalindromeSubseq(Strings){StringtnewStringBuilder(s).reverse().toString();intns.length();int[][]dpnewint[n1][n1];for(inti1;in;i){for(intj1;jn;j){if(s.charAt(i-1)t.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]);}}}returndp[n][n];}}这个方法的妙处在于你学一个 LCS就白赚一道回文子序列血赚不亏。六、三种解法对比总结解法核心思想时间空间面试推荐度二维 DP区间动态规划O(n²)O(n²)⭐⭐⭐⭐⭐ 必会一维 DP滚动数组优化O(n²)O(n)⭐⭐⭐⭐ 加分项LCS 转化问题转化O(n²)O(n²)⭐⭐⭐⭐ 展示知识广度七、写在最后动态规划就像谈恋爱——先解决小问题再解决大问题。单个字符是回文长度为1→ 两个字符能匹配吗 → 三个字符呢 → 最后搞定整个字符串。每一步都依赖前面已经算好的结果就像每一段稳定的感情都建立在之前的经历之上。至于空间优化那就是学会断舍离——丢掉没用的东西只保留真正需要的。所以下次面试官问你这道题你可以自信地说“这道题我有三种解法。第一种是标准的区间 DP第二种优化到 O(n) 空间第三种转化为 LCS。您想听哪一种”然后看着面试官满意的微笑知道自己稳了。参考资料LeetCode 516. Longest Palindromic Subsequence《算法导论》第15章 动态规划如果这篇文章对你有帮助欢迎点赞收藏转发三连你的支持是我写下去的最大动力我们下期见拜拜