常考数据结构与算法:最长回文子串
暴力解法:
列举所有的子串，判断是否为回文串,保存最长的回文串。
/** 暴力解法: 列举所有的子串，判断是否为回文串,保存最长的回文串。*/public int getLongestPalindrome(String A, int n) {if(n == 0 || n == 1)return n;int count = 0;String temp;for (int i = 0; i < n; i++) {for (int j = i+1; j <= n; j++) {// 截取字符串temp = A.substring(i,j);// 判断字符串是否为回文if(isPalindrome(temp) && (j-i) > count){count = j-i;}}}return count;}private boolean isPalindrome(String str){int start=0;int end=str.length()-1;while(start<end){if(str.charAt(start) == str.charAt(end)){start++;end--;}else{return false;}}return true;}
动态规划(利用已有的信息，判断下一步)
暴力解法时间复杂度太高，我们可以考虑，去掉一些暴力解法中重复的判断。
首先定义：字符串 s 从下标 i 到下标 j 的字串为 P(i, j)，若 s 从下标 i 到下标 j 的字串为回文串，则 P(i, j) = true，否则 P(i, j) = false。如下图所示：
则 P(i, j) = (P(i + 1, j - 1) && s[i] == s[j])。
所以如果我们想知道 P（i,j）的情况，不需要调用判断回文串的函数了，只需要知道 P（i+1，j−1）的情况就可以了，这样时间复杂度就少了 O(n)。因此我们可以用动态规划的方法，空间换时间，把已经求出的 P（i，j）存储起来。
如果 s[i+1, j-1] 是回文串，那么只要 s[i] == s[j]，就可以确定 s[i, j] 也是回文串了。
注意：
求 长度为 1 和长度为 2 的 P(i, j) 时不能用上边的公式，因为我们代入公式后会遇到 P[i][j] 中 i > j 的情况，比如求P[1][2] 的话，我们需要知道 P[1+1][2-1]=P[2][1] ，而 P[2][1] 代表着 S[2, 1] 是不是回文串，这显然是不对的，所以我们需要单独判断。
所以我们先初始化长度是 1 的回文串的 P [i , j]，这样利用上边提出的公式 P(i,j)=(P(i+1,j-1) && S[i]==S[j])，然后两边向外各扩充一个字符，长度为 3 的，为 5 的，所有奇数长度的就都求出来了。同理，初始化长度是 2 的回文串 P[i,i+1]，利用公式，长度为 4 的，6 的所有偶数长度的就都求出来了。
public int getLongestPalindrome(String A, int n) {int sLen = n;int maxLen = 0;String ans = "";boolean[][] P = new boolean[sLen][sLen];// 遍历所有长度 "abc1234321"for (int len = 1; len <= sLen; len++) {for (int start = 0; start < sLen; start++) {int end = start + len - 1;// 下标越界，结束循环if (end >=sLen) {break;}P[start][end] = (len == 1 || len == 2 || P[start + 1][end - 1]) && A.charAt(start) == A.charAt(end);if (P[start][end] && len > maxLen) {maxLen = len;ans = A.substring(start, end + 1);}}}return ans.length();}
《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读
总结
以上是生活随笔为你收集整理的常考数据结构与算法:最长回文子串的全部内容，希望文章能够帮你解决所遇到的问题。
- 上一篇： linux:内核中断
- 下一篇： 常考数据结构与算法:输出二叉树的右视图