LeetCode

链接

LeetCode_5_最长回文子串

题目

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

示例 1：

输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd" 输出: "bb"

思路

思路一、动态规划

假设字符串("babab")为s, 它的长度为n dp是大小为 n * n 的二维数组, dp[i][j] 表示s[i,j]是否为回文串, 存储true, false

如何求出dp[i][j]的值? 分两种情况 ① 如果s[i,j]的长度(j - i + 1) <= 2时:      如果s[i]等于s[j], 那么s[i,j]是回文串, 所以dp[i][j] = s[i] == s[j] ② 如果s[i,j]的长度(j - i + 1) > 2时:     如果s[i+1, j-1]是回文串, 并且s[i]等于s[j], 那么s[i,j]是回文串, 所以dp[i][j] = dp[i+1, j-1] && ( s[i] == s[j-1] )

时间复杂度: O(n^2), 空间复杂度: O(n^2)

代码实现

/** * 1.动态规划 * dp(i,j): 表示字符串[i,j]范围是否为回文串, 是的话存储true, 不是存储false * dp(0,0) = true, dp(1,1) = true,dp(2,2) = true... * dp(i,j) 如果s[i,j]的长度小于2时: if(s[i] == s[j]) s[i,j] = true * else dp[i,j] = false * 如果s[i,j]的长度大于2时: if(dp[i+1,j-1] == true) s[i,j] = (dp[i+1,j-1] && s[i] == s[j]) * else dp[i,j] = false */ public String longestPalindrome(String s) { if (s == null) return ""; char[] cs = s.toCharArray(); int len = cs.length; if(len <= 1) return s; boolean[][] dp = new boolean[len][len]; int maxLen = 1; int begin = 0; //状态转移计算 for (int i = len-1; i >= 0; i--) { for (int j = i; j < len; j++) { int currLen = j-i+1; if(currLen <= 2){ //如果子串长度不超过2 dp[i][j] = cs[i] == cs[j]; }else{ //如果子串长度超过2 dp[i][j] = dp[i+1][j-1] && (cs[i] == cs[j]); } if(dp[i][j] && currLen > maxLen){ maxLen = currLen; begin = i; } } } return new String(cs,begin,maxLen); }

 

思路二、扩展回文串中心

假设字符串 (“abbaba”) 的长度为 n, 那么一共有n + (n-1) == 2n - 1 个扩展中心

时间复杂度: O(n^2),  空间复杂度: O(1)

代码实现

/** * 思路: 扩展中心, 以每个字符作为回文串中心向两边扩展 */ public String longestPalindrome(String s) { if (s == null) return null; char[] cs = s.toCharArray(); if (cs.length <= 1) return s; int maxLen = 1; // 最长回文子串的长度（至少是1） int begin = 0; // 最长回文子串的开始索引 /** * 1.除去第一个和最后一个元素,以中间这些元素作为回文子串的中心向两边扩展 * 2.以每两个元素之间的间隙作为中心向两边扩展 */ for (int i = cs.length - 2; i >= 1; i--) { // 以字符为中心向左右扩展(倒序遍历) | 以字符左边的间隙为中心向左右扩展(正序遍历) int len1 = palindromeLength(cs, i - 1, i + 1); // 以字符右边的间隙为中心向左右扩展(倒序遍历) | 以字符为中心向左右扩展(正序遍历) int len2 = palindromeLength(cs, i, i + 1); len1 = Math.max(len1, len2); //更新最长回文子串的长度以及子串起始位置 if (len1 > maxLen) { maxLen = len1; //如果回文串长度是偶数,那么说明中心在为两个元素之间的间隙; 如果是奇数, 那么中心在中间的元素; begin = i - ((maxLen - 1) >> 1); } } // 以0号字符右边的间隙为中心的最长回文子串长度是2 if (cs[0] == cs[1] && maxLen < 2) { // cs[0, 1]就是最长的回文子串 begin = 0; maxLen = 2; } return new String(cs, begin, maxLen); } /** * @return 从l开始向左、从r开始向右扫描，获得的最长回文子串的长度 */ private int palindromeLength(char[] cs, int l, int r) { while (l >= 0 && r < cs.length && cs[l] == cs[r]) { l--; r++; } return r - l - 1; }

 

思路三、扩展回文串中心优化

优化点: 由连续的相同字符组成的子串作为扩展中心

比如, 字符串"babbbabaa"的扩展中心有: "b", "a", "bbb", "a", "b", "aa"

核心逻辑:    找到右边第一个不等于s[ i ]的字符, 记为位置 r, i 左边位置记为 l   r作为下一次的 i,  由 l 开始向左, r 开始向右扩展, 找到最长的回文子串

代码实现

/** * 扩展中心法优化: 由连续的相同字符组成的子串作为扩展中心 * 字符串"babbbabaaa"的扩展中心有: "b","a","bbb","a","b","aa" */ public static String longestPalindrome_(String s) { if (s == null) return null; char[] cs = s.toCharArray(); if (cs.length <= 1) return s; int maxLen = 1; // 最长回文子串的长度（至少是1） int begin = 0; // 最长回文子串的开始索引 int i = 0; while (i < cs.length) { //从左向右遍历数组 int l = i - 1; //暂存当前中心的左边界 /** * 寻找扩展中心, 即:找到右边第一个不等于cs[i]的位置 */ int r = i; while (++r < cs.length && cs[r] == cs[i]); i = r; //已确认当前扩展种中心字符串的左右边界, 那么下一次遍历时,下一个扩展中心的左边界就是i // 从l向左，从r向右扩展 while (l >= 0 && r < cs.length && cs[l] == cs[r]) { l--; r++; } // 扩展结束后，cs[l + 1, r)就是刚才找到的最大回文子串 // ++l后，l就是刚才找到的最大回文子串的开始索引 int len = r - ++l; if (len > maxLen) { maxLen = len; begin = l; } } return new String(cs, begin, maxLen); }

 

思路四、Manacher算法

定义

中间的 # 字符可以是任意字符, 头部的^字符、尾部的$字符，必须是原字符串中不包含的字符 m[i]的含义:  ①是以cs[ i ]为扩展中心的最大回文子串的长度(不包括#字符)   最大回文子串在原字符串中的开始索引: ( i - m[ i ] ) >> 1 ②是以cs[ i ]为扩展中心的最大回文子串的右半部分或左半部分的长度（包含 # 字符）   所以，Manacher算法的关键在于求出m数组

情景1

已知 索引l, li, c, i, r的值分别为1, 4, 6, 8, 11;  cs[ l, r ]是以c为中心的最大回文串; i, li 以 c 为中心对称, m[i]是待求项 因为:    m[li] == 1,  i + m[li] < r 由于回文的对称性, 得出结论:   m[i] = m[li],  即: m[i] == 1

情景2

已知:    m[ li ] == 3, i + m[ li ] == r 结论:    m[ i ]至少是m[ li ], 也就是说, 至少是3   接下来利用扩展中心法以i为中心计算出m[ i ]   当 i + m[i] > r 时, 更新c, r      c = i, r = i + m[i]

情景3

已知:   m[ li ] == 5, i + m[ li ] > r 结论:   m[ i ]至少是r - i, 也就是说, 至少是3   接下来利用扩展中心法以 i 为中心计算出 m[i]   当i + m[i] > r 时, 更新 c, r     c = i, r = i + m[i]

情景4

当 i == r 时   直接利用扩展中心法以 i 为中心计算出m[i] 当 i + m[i] > r时, 更新c, r   c = i, r = i + m[i]

代码实现

/** * 思路: Manacher算法, 最优解 */ public String longestPalindrome(String s) { if (s == null) return null; char[] oldCs = s.toCharArray(); if (oldCs.length <= 1) return s; // 预处理 char[] cs = preprocess(oldCs); // 构建m数组 int[] m = new int[cs.length]; int c = 1, r = 1, lastIdx = m.length - 2; int maxLen = 0, idx = 0; for (int i = 2; i < lastIdx; i++) { if (r > i) { int li = (c << 1) - i; m[i] = (i + m[li] <= r) ? m[li] : (r - i); } // 以i为中心，向左右扩展 while (cs[i + m[i] + 1] == cs[i - m[i] - 1]) { m[i]++; } // 更新c、r if (i + m[i] > r) { c = i; r = i + m[i]; } // 找出更大的回文子串 if (m[i] > maxLen) { maxLen = m[i]; idx = i; } } int begin = (idx - maxLen) >> 1; return new String(oldCs, begin, maxLen); } private char[] preprocess(char[] oldCs) { char[] cs = new char[(oldCs.length << 1) + 3]; cs[0] = '^'; cs[1] = '#'; cs[cs.length - 1] = '$'; for (int i = 0; i < oldCs.length; i++) { int idx = (i + 1) << 1; cs[idx] = oldCs[i]; cs[idx + 1] = '#'; } return cs; }