Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
翻译：
找出字符串s中最长的回文子串，字符串s的最长是1000，假设存在唯一的最长回文子串
法一：直接暴力破解
O(N3)的时间复杂度，运行超时：
Java程序：
public class Solution {
public String longestPalindrome(String s) {
// isPalindrome(s);
int sLen = s.length();
int maxLen = 0;
String maxSubStr="";
if(sLen==1) return s;
for(int i=0;i<sLen;i++){
for(int j=i+1;j<sLen-1;j++){
String subStr = s.substring(i,j+1);
if(isPalindrome(subStr)){
int tmp = subStr.length();
if(tmp >maxLen){
maxLen = tmp;
maxSubStr = subStr;
}
}
}
}
return maxSubStr;
}
boolean isPalindrome(String s){
int sLen = s.length();
if(sLen==1) return true;
for(int i = 0;i<sLen/2;i++){
char left = s.charAt(i);
char right = s.charAt(sLen - i -1);
if(left!=right)
return false;
}
return true;
}
}
法二：
网上找个O（N2）
定义一个dp矩阵 长度是字符串s的长度
初始值问题：
对角线设为1
为了防止回文序列长度是偶数要对s[i] 与s[i+1]相等作判断
若s[i]== s[j],则dp[i][j] = 1
对于s[i] 到s[j] 部分是否是回文字符串，需要考虑的是s[i+1]到s[j-1]部分是不是回文
可以转化为：若s[i] == s[j] ,则考虑s[i+1] 是否等于s[j-1]，这里只需判断最近的一个就好了，因为这是从里面向外面循环的
对于dp矩阵的元素就是：若dp[i][j] = 1，则考虑d[i+1][j-1]是否等于 1,若d[i+1][j-1]=0,则 ，令dp[i][j]=0，里面不回文外面一定不回文。
public String longestPalindrome(String s){
if(s==null) return null;
if(s.length()<=1) return s;
int sLen = s.length();
int maxLen = 1;
String longest = null;
int[][] dp = new int[sLen][sLen];
// 对角线 1
for(int i=0;i<sLen;++i)
dp[i][i]=1;
// 相邻元素是否相等，主要是用来判断回文长度是偶数
for(int i=0;i<sLen-1;++i){
if(s.charAt(i)==s.charAt(i+1)){
dp[i][i+1] = 1;
longest = s.substring(i,i+2);
}
}
// 依次遍历所有可能长度的回文数
for(int k=2;k<sLen;++k){
for(int i=0;i<sLen-k;++i){
int j = i+k;
if(s.charAt(i) == s.charAt(j)){
dp[i][j] = dp[i+1][j-1];
if(dp[i][j]==1 && k>maxLen)
longest = s.substring(i,j+1);
}else
dp[i][j]=0;
}
}
return longest;
}
Time Limit Exceeded
Last executed input:
"cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc"
这里是全部一样的，执行超时。
增加一个集合用于判断字符串中元素全部一样的情况
运行依旧超时
public class Solution {
String longestPalindrome(String s){
if(s==null) return null;
if(s.length()<=1) return s;
int sLen = s.length();
int maxLen = 1;
String longest = null;
TreeSet ts = new TreeSet();
for(int i=0;i<sLen;i++)
ts.add(s.charAt(i));
if(ts.size()==1) return s;
int[][] dp = new int[sLen][sLen];
// 对角线 1
for(int i=0;i<sLen;++i)
dp[i][i]=1;
// 相邻元素是否相等，主要是用来判断回文长度是偶数
for(int i=0;i<sLen-1;++i){
if(s.charAt(i)==s.charAt(i+1)){
dp[i][i+1] = 1;
longest = s.substring(i,i+2);
}
}
// 依次遍历所有可能长度的回文数
for(int k=2;k<sLen;++k){
for(int i=0;i<sLen-k;++i){
int j = i+k;
if(s.charAt(i) == s.charAt(j)){
dp[i][j] = dp[i+1][j-1];
if(dp[i][j]==1 && k>maxLen)
longest = s.substring(i,j+1);
}else
dp[i][j]=0;
}
}
return longest;
}
}
依旧超时：
Last executed input:aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabcaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
法三：
时间复杂度：O(N2)
空间复制度：O(1)
也是来源于上面链接中的程序
这里的思想是：对应字符串中的i位置，向两侧依次判断是否相等，遇到第一个不相等的时候，结束判断
对应最大回文长度是偶数的，要先判断s[i]与s[i+1]是否相等后，再作上面类似的操作
这个AC了
class Solution{
String longestPalindrome(String s){
if(s.isEmpty()) return null;
if(s.length() == 1) return s;
String longest = s.substring(0,1);
for(int i=0;i<s.length();++i){
// 这里考虑的是回文长度是奇数的情况
String tmp = longestPalindromeCenter(s,i,i);
if(tmp.length() > longest.length())
longest = tmp;
//偶数时候
if(i<s.length() -1 && s.charAt(i)==s.charAt(i+1) ){
tmp = longestPalindromeCenter(s,i,i+1);
if(tmp.length() > longest.length())
longest = tmp;
}
}
return longest;
}
String longestPalindromeCenter(String s,int left,int right){
while(left>=0 && right< s.length() && s.charAt(left)== s.charAt(right)){
left--;
right++;
}// 以s[i] 为中心向两侧扩展，直到不满足回文的条件结束
return s.substring(left+1,right);// 结束的时候已经执行了left-- right++ 要去掉
}
}
上面的对于是偶数的可以不要判断，因为在下面的while中有先对这个两个起始点的判断了
对应的Python程序：
class Solution(object):
def longestPalindrome2(self, s):
longest = ''
if len(s)<=1 : return s
sLen = len(s)
for i in range(sLen):
tmp = self.longestPalindromeCenter(s,i,i)
if len(tmp) > len(longest):
longest = tmp
# if i<sLen-1 and s[i]==s[i+1]:
# tmp = self.longestPalindromeCenter(s, i, i+1)
# if len(tmp)>len(longest):
# longest = tmp
# if i<sLen-1 and s[i]==s[i+1]:
tmp = self.longestPalindromeCenter(s, i, i+1)
if len(tmp)>len(longest):
longest = tmp
return longest def longestPalindromeCenter(self, s,left,right):
while(left>=0 and right<len(s) and s[left]==s[right]):
left-=1
right+=1
return s[(left+1):right] def longestPalindrome(self, s):
if len(s)<=1: return s
sLen = len(s)
dp = [[0 for _ in range(sLen)] for _ in range(sLen)]
longest=""
for i in range(sLen):
dp[i][i] = 1
for i in range(sLen-1):
if s[i]==s[i+1]:
dp[i][i+1] = 1
longest = s[i:(i+2)]
for k in range(2,sLen):
for i in range(0,sLen-k):
j = i + k
if s[i]==s[j]:
dp[i][j]=dp[i+1][j-1]
if dp[i][j]==1 and len(s[i:(j+1)])>len(longest):
longest = s[i:(j+1)]
else:
dp[i][j] = 0
return longest
依旧是根据中心点查找的AC，下面一个时间超时
附几个让你超时的测试字符串：
String s1="aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabcaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
String s2="cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc";
String s3 = "vmqjjfnxtyciixhceqyvibhdmivndvxyzzamcrtpywczjmvlodtqbpjayfchpisbiycczpgjdzezzprfyfwiujqbcubohvvyakxfmsyqkysbigwcslofikvurcbjxrccasvyflhwkzlrqowyijfxacvirmyuhtobbpadxvngydlyzudvnyrgnipnpztdyqledweguchivlwfctafeavejkqyxvfqsigjwodxoqeabnhfhuwzgqarehgmhgisqetrhuszoklbywqrtauvsinumhnrmfkbxffkijrbeefjmipocoeddjuemvqqjpzktxecolwzgpdseshzztnvljbntrbkealeemgkapikyleontpwmoltfwfnrtnxcwmvshepsahffekaemmeklzrpmjxjpwqhihkgvnqhysptomfeqsikvnyhnujcgokfddwsqjmqgsqwsggwhxyinfspgukkfowoxaxosmmogxephzhhy";