Kimi LeetCode 3504. 子字符串连接后的最长回文串 II Java实现

以下是 LeetCode 3504. 子字符串连接后的最长回文串 II 的 Java 实现javaclass Solution {/*** LeetCode 3504. 子字符串连接后的最长回文串 II** 思路* 1. 回文串可以只来自 s或只来自 t或来自 s t 的拼接* 2. 对于 s t 的拼接情况设从 s 取子串 sub_s从 t 取子串 sub_t* 拼接后为回文串则 sub_s 的后缀必须和 sub_t 的前缀镜像匹配* 3. 将 t 反转后问题转化为找 s 和 reversed(t) 的公共子串* 4. 预处理 g1[i] 和 g2[i]分别以 s[i] 和 reversed(t)[i] 开始的最长回文子串长度* 5. 用 DP 找 s 和 reversed(t) 的最长公共后缀然后尝试在中间扩展回文** 时间复杂度O(m * n m^2 n^2)其中 m s.length, n t.length* 空间复杂度O(m * n)*/public int longestPalindrome(String S, String T) {char[] s S.toCharArray();// 将 T 反转这样找 t 的前缀匹配就变成了找 reversed(t) 的后缀匹配char[] t new StringBuilder(T).reverse().toString().toCharArray();int m s.length, n t.length;// g1[i] s 中以位置 i 开始的最长回文子串长度// g2[i] reversed(t) 中以位置 i 开始的最长回文子串长度int[] g1 calc(s), g2 calc(t);// 初始化答案最长回文可能只来自 s 或只来自 tint ans 0;for (int x : g1) ans Math.max(ans, x);for (int x : g2) ans Math.max(ans, x);// f[i][j] s[0..i-1] 和 t[0..j-1] 的最长公共后缀长度// 即 s 以 i-1 结尾、reversed(t) 以 j-1 结尾的匹配长度int[][] f new int[m 1][n 1];for (int i 1; i m; i) {for (int j 1; j n; j) {if (s[i - 1] t[j - 1]) {f[i][j] f[i - 1][j - 1] 1;// 情况1匹配部分 s 中剩余回文// f[i][j] * 2匹配字符在回文两侧各出现一次// g1[i]从 s[i] 开始的最长回文作为回文中心ans Math.max(ans, f[i][j] * 2 (i m ? g1[i] : 0));// 情况2匹配部分 reversed(t) 中剩余回文// g2[j]从 reversed(t)[j] 开始的最长回文作为回文中心ans Math.max(ans, f[i][j] * 2 (j n ? g2[j] : 0));}}}return ans;}/*** 中心扩展法从 (l, r) 向两边扩展更新以 l 开始的最长回文长度*/private void expand(char[] s, int[] g, int l, int r) {while (l 0 r s.length s[l] s[r]) {g[l] Math.max(g[l], r - l 1);--l;r;}}/*** 计算字符串中每个位置开始的最长回文子串长度* 对每个位置分别尝试奇数长度和偶数长度的中心扩展*/private int[] calc(char[] s) {int n s.length;int[] g new int[n];for (int i 0; i n; i) {// 奇数长度回文单字符中心expand(s, g, i, i);// 偶数长度回文双字符中心expand(s, g, i, i 1);}return g;}}算法思路回文串的来源有三种可能情况 说明仅来自 s sub_t 为空sub_s 本身是回文仅来自 t sub_s 为空sub_t 本身是回文s t 拼接 sub_s 的后缀与 sub_t 的前缀镜像对称关键洞察对于拼接情况若 sub_s sub_t 是回文则 sub_s 的末尾部分必须和 sub_t 的开头部分镜像匹配。将 t 反转后这转化为找 s 和 reversed(t) 的公共子串问题。预处理 g1[i] / g2[i]用中心扩展法求以每个位置开始的最长回文子串长度。这些值用于在匹配部分的中间扩展额外的回文中心。动态规划f[i][j] 表示 s[0..i-1] 和 reversed(t)[0..j-1] 的最长公共后缀长度。每当 s[i-1] reversed(t)[j-1] 时- f[i][j] * 2匹配字符在回文两侧各出现一次- g1[i] 或 g2[j]在中间附加额外的回文中心复杂度预处理 O(m^2 n^2)DP 部分 O(m \times n)空间 O(m \times n)。