LeetCode.5-最长回文子串(Longest Palindromic Substring)

柔情只为你懂 2022-01-07 11:59 285阅读 0赞

这是悦乐书的第**342**次更新，第**366**篇原创

### 01 看题和准备 ###

今天介绍的是LeetCode算法题中Medium级别的第3题（顺位题号是5）。给定一个字符串s，找到s中最长的回文子字符串。 您可以假设s的最大长度为1000。例如：

输入：“babad”  
输出：“bab”  
注意：“aba”也是一个有效的答案。

输入：“cbbd”  
输出：“bb”

### 02 第一种解法 ###

暴力解法。  
使用两层循环截取出所有的子串，判断该子串是否是回文，从中取长度最长的子串作为结果输出。  
此解法时间复杂度是`O(N^3)`，空间复杂度是`O(1)`。

public String longestPalindrome(String s) { int max = 0, n = s.length(); String result = ""; for (int i=0; i<n; i++) { for (int j=i+1; j<=n; j++) { String tem = s.substring(i,j); if (isPalindrome(tem)) { if (j-i > max) { max = j-i; result = tem; } } } } return result; } public boolean isPalindrome(String s){ int left = 0, right = s.length()-1; while (left < right) { if (s.charAt(left) != s.charAt(right)) { return false; } left++; right--; } return true; }

### 03 第二种解法 ###

我们也可以换一种找回文的方式，从左右两边向中间变成由中间向左右两边。

此时需要考虑回文的长度是奇数还是偶数的情况，如果是奇数形回文，就以当前字符为中心左右两边寻找，例如回文"bab"；如果是偶数形回文，需要两个字符，并且这两个字符是相等的，则需要以当前字符和其相邻的字符为中心向左右两边寻找，例如回文"abba"。

此解法的时间复杂度是`O(N^2)`，空间复杂度是`O(1)`。

public String longestPalindrome2(String s) { if (s.length() < 2) { return s; } int n = s.length(), start = 0, end = 0; for (int i=0; i<n-1; i++) { int len = helper(s, i, i); int len2 = helper(s, i, i+1); int len3 = Math.max(len, len2); if (len3 > end - start) { start = i - (len3-1)/2; end = i + len3/2; } } return s.substring(start, end+1); } /** * 以当前字符为中心向左右两边扩散，寻找回文子串 * @param s 字符串 * @param left 起始索引 * @param right 结束索引 * @return 回文子串长度 */ public int helper(String s, int left, int right) { int n = s.length(), L = left, R = right; while (L >= 0 && R < n && s.charAt(L) == s.charAt(R)) { // 继续向左寻找 L--; // 继续向右寻找 R++; } return R - L -1; }

### 04 第三种解法 ###

动态规划算法，用空间换时间，是对第一种解法的改进。  
此解法的时间复杂度是`O(N^2)`，空间复杂度是`O(N^2)`。

public String longestPalindrome3(String s) { if (s.length() < 2) { return s; } int n = s.length(), start = 0, end = 0; int maxLen = 0; // dp[j][i]表示子串[j,i]是回文 boolean[][] dp = new boolean[n][n]; // 右边界 for (int i=0; i<n; i++) { // 左边界 for (int j=i; j>=0; j--) { if (i == j) { dp[j][i] = true; } else if (s.charAt(i) == s.charAt(j)) { // 回文中至少3个字符 if (j < i-1) { dp[j][i] = dp[j+1][i-1]; } else { dp[j][i] = true; } } else { dp[i][j] = false; } // 比较最大值，并重新赋值 if (i-j+1 > maxLen && dp[j][i]) { maxLen = i-j+1; start = j; end = i; } } } return s.substring(start, end+1); }

### 05 第四种解法 ###

马拉车算法(Manacher's Algorithm)，来自于讨论区，这是第一次听说这种算法，将时间复杂度降低到了`O(N)`，也是很厉害了，后续抽时间来详细了解下这个算法。

public String longestPalindrome4(String s) { String T = preProcess(s); int n = T.length(); int[] P = new int[n]; int C = 0, R = 0; for (int i = 1; i < n - 1; i++) { int i_mirror = 2 * C - i; if (R > i) { P[i] = Math.min(R - i, P[i_mirror]); } else { P[i] = 0; } while (T.charAt(i + 1 + P[i]) == T.charAt(i - 1 - P[i])) { P[i]++; } if (i + P[i] > R) { C = i; R = i + P[i]; } } int maxLen = 0; int centerIndex = 0; for (int i = 1; i < n - 1; i++) { if (P[i] > maxLen) { maxLen = P[i]; centerIndex = i; } } int start = (centerIndex - maxLen) / 2; return s.substring(start, start + maxLen); } /** * * @param s * @return */ public String preProcess(String s) { int n = s.length(); if (n == 0) { return "^$"; } String ret = "^"; for (int i = 0; i < n; i++) { ret += "#" + s.charAt(i); } ret += "#$"; return ret; }

### 06 小结 ###

算法专题目前已连续**日更超过六个月**，算法题文章**211**\+篇，公众号对话框回复【**数据结构与算法**】、【**算法**】、【**数据结构**】中的任一关键词，获取系列文章合集。

以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！

转载于:https://www.cnblogs.com/xiaochuan94/p/10965748.html