import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 方式一:动态规划 * @param A string字符串 * @return int整型 */ public int getLongestPalindrome (String s) { // write code here if (s == null) return 0; char[] cs = s.toCharArray(); if (cs.length <= 1) return 1; // 记录以下两个值可截取最后的回文子串 // 记录最长回文子串长度(至少是1) int maxLen = 1; // 记录最长回文子串开始索引 int begin = 1; boolean[][] dp = new boolean[cs.length][cs.length]; // 从下到上(i由大到小)遍历 for (int i = cs.length - 1; i >= 0; i--) { // 从左到右(j由小到大),因为i必须小于等于j,不可能i>j(字符串反向了) for (int j = i; j < cs.length; j++) { // cs[i,j]的长度 int len = j - i + 1; // 判断是否为回文子串,两种可能 // 第一种:俩值相等,且长度小于等于2, // 第二种:俩值相等,里面的子串也是回文串(子串已经推导出来过的值) dp[i][j] = (cs[i] == cs[j]) && (len <= 2 || dp[i + 1][j - 1]); // 如果是回文子串,判断子串长度,重置最大值和开始索引 if (dp[i][j] && len > maxLen) { maxLen = len; begin = i; } } } return maxLen; } } /** * 方式二:扩展中心法 */ public String longestPalindromeEx(String s) { if (s == null) return null; char[] cs = s.toCharArray(); if (cs.length <= 1) return s; // 最长回文子串的长度(至少是1) int maxLen = 1; // 最长回文子串的开始索引 int begin = 0; 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; } /** * 方式三:扩展中心法2 */ public static String longestPalindromeEx2(String s) { if (s == null) return null; char[] cs = s.toCharArray(); if (cs.length <= 1) return s; // 最长回文子串的长度(至少是1) int maxLen = 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]); // r会成为新的i i = r; // 从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); } /** * 马拉车算法 */ // 预处理 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; } // 算法根髓 public String longestPalindromeManacher(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); }
解题思想:动态规划,形成dp数组,倒立根据已知解求未知,然后比较最值,推导下一个的最值。
* 方式一:动态规划
* 方式二:扩展中心法--扫描值及值间隙作为中心扩展点
* 方式三:扩展中心法优化--相同数据合体作为中心扩展点
* 方式四:马拉车算法