思路:
分两种情况考虑:
第一种:奇数回文,比如:“aba”
第二种:偶树回文 ,比如:“adda”
然后遍历字符串,以该字符为中心,检查它的前后能够构成上述两种情况中的
回文串。
时间复杂度: O(n ^2)
代码:
public class Solution { //最长回文子串 public String longestPalindrome(String s) { int len = s.length(); if(len == 1) return s; int maxLen = 0; String ps =""; for(int i = 1 ; i < len ; i++) { int low = i - 1; int high = i + 1; // 奇数回文 以s[i]为中心.. 查看它的左右两边是否满足回文 int count = 0; while(low >= 0 && high < len && s.charAt(low) == s.charAt(high)) { count = high - low + 1; low--; high++; } if(count > maxLen) { ps = s.substring(i - count/2 , i + count/2 + 1); maxLen = count; } //检查完奇数后,立马检查是否满足偶数 其实如果满足的话,一定该回文串所有字符相等 // 偶数回文 count = 0; low = i - 1; high = i; while(low >= 0 && high < len && s.charAt(low) == s.charAt(high)) { count = high - low + 1; low--; high++; } if(count > maxLen) { ps = s.substring(i - count/2 , i + count/2); maxLen = count; } } return ps; } }
动态规划求解:
思路:
对于字符串"aXa" , 如果子串X为回文串,那么aXa就是回文串
X不是回文串,那么"aXa"也一定不是回文串
所以,可以用一个状态转移方程,来存放子串是否为回文;
matrix[i][j]的意思就是 字符串中i到j是否为回文串
注意这里 i >= j的,也就是说,最后的结果矩阵只有一半。
状态转移方程:
matrix[i][j] = 1 // i = j
matrix[i][j] = s[i] == s[j] // i = j - 1 i j 相邻 只要两者相等即可
matrix[i][j] = s[i]==s[j] && matrix[i + 1][ j - 1] // 其他情况
观察这个递归式,可知,matrix[i][j] 要利用到matrix[i + 1][j - 1]
所以,这次不能一行一行的求出值,而应当一列一列的求值。
代码:
public static String longestPalindrome(String s) { int len = s.length(); boolean[][] matrix = new boolean[len][len]; int maxLen = 1; int start = 0; //初始化 for(int i = 0; i < len ; i++) { matrix[i][i] = true; } for(int col = 1 ; col < len ; col++) { for(int row = col - 1; row >= 0 ; row--) { if(s.charAt(col) == s.charAt(row)) { //row col 不相邻 但是 子串不回文 if(row + 1 < col - 1 && !matrix[row + 1][col - 1]) { matrix[row][col] = false; continue; } matrix[row][col] = true; int length = col - row + 1; if(length > maxLen) { maxLen = length; start = row; } } } } return s.substring(start,start+maxLen); }
相关推荐
最长回文子串
输入一个字符串,求出其中最长的回文子串。子串的含义是:在原串中连续出现的字符串片段。回文的含义是:正着看和倒着看相同,如abba和xyyxyyx。在判断时,应该忽略所有标点符号和空格,且忽略大小写,但输出应该...
自己编的,望大家指点!这是西工大期末考试的题目,做了好久才做出来
查找一个字符串中的最长回文子串,这里采用的是Manacher算法 比如:cababcaac的最长回文子串就是caac 其中的aba bab也都是回文子串 (Manacher算法) 效率很高的一种查找算法,效率可以达到O(2n+1)
leetcode刷题宝典
最长回文子串.md
最长回文子串(dp)1
一个算法中的经典问题,求最长回文子串问题,其实是可以归于二维动态规划问题。 对于给定的一个字符串中,找到这个字符串中的回文子串,回文子串的概念是从前往后正向的读和从后往前反向的读都是完全相同的字符串。
c# c#_Leetcode面试题解之第5题最长回文子串
c语言 C语言_C语言编程基础之leetcode题解第5题最长回文子串
c++ c++_c++编程基础之leetcode题解第5题最长回文子串
字符串处理- 回文串相关- 求最长回文子串.rar
java面试 java面试_leetcode面试java编程题解之第5题最长回文子串_java题解
4.2.3 使用Manacher算法求最长回文子串.pdf
原创:leetcode 5. 最长回文子串//寻找以i-1,i为中点偶数长度的回文//寻找以i为中心的奇数长度的回文。
最长回文子串问题:给定一个字符串,求它的最长回文子串长度。如果一个字符串正着读和反着读是一样的,那它就是回文串。今天我们就来探讨下这个问题