Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

最开始的采用了很暴力的方法如下：

class Solution {    public String longestPalindrome(String s) {        int i=0,j=0,length=s.length(),maxlength=0;        int rei=0,rej=0;        for (i=0;i
     
      maxlength)                        {                            maxlength=j+1-i;                            rei=i;                            rej=j+1;                        }                         }                }            }        }        return s.substring(rei,rej);    }    boolean isPalin(String s)    {        int length=s.length();        for(int i=0;i
     

method isPalin()判断一个子字符串是否为回文的。

一个回文的字符串必定首尾相同，通过这个规律先减小部分计算量，只对首尾相同的子字符串判断是否回文。

简单的字符串可以应对，无规律的字符串也可以大程序减小计算量，但是对于bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb这种没有任何作用，运行结果：Time limitted exceeded。

LeetCode可以接受的时间复杂度为O（n^2），必须要采用一些策略：

1、对于一个从i到j的回文序列，它从i+1到j-1也必定是回文序列，可以利用这个方案提升效率。

2、从回文序列的中心下手。

提升效率后的代码：

 

//答案的算法class Solution {    public String longestPalindrome(String s)     {        int i=0,length=s.length();        int maxlength=0,templength=0,center=0;        //中心在左边的情况        for (i=0;i
     
      =0)        {            if(s.charAt(i)==s.charAt(length-i-1))                i--;            else                break;                        }        if(length%2==0)            return 2*(half-i);        else             return 2*(half-i)-1;    }}
     

Palin(s.substring(i-length+1,length));

return s.substring(center/2-maxlength/2,center/2-maxlength/2+maxlength);

mad，水平好低，思路很简单，但是边界值处理要头脑清晰才行，上面两句调试了一段时间。