解決方法一：
思路是找到所有的子序列判斷虚缎，中間有個if(s.charAt(i)==s.charAt(j))是判斷如果這個子序列的兩端不相等的話就不用判斷了炉峰，節(jié)省運(yùn)行時間徽龟。但還是用到了兩個for循環(huán)蟋软，運(yùn)行提交時時間超標(biāo)祷安。這個方法有改進(jìn)的話歡迎探討姥芥。
注意小點(diǎn)：s.substring(i,j);是包括i不包括j即[i,j)
class Solution {
? ? public String longestPalindrome(String s) {
? ? ? ? int ans=0;
? ? ? ? int temp=0;
? ? ? ? if(s.length()==0) return s;
? ? ? ? if(s.length()==1) return s;
? ? ? ? char c=s.charAt(0);
? ? ? ? String anss=String.valueOf(c);
? ? ? ? for(int i=0;i<s.length();i++){
? ? ? ? ? ? for(int j=i+1;j<s.length();j++){
? ? ? ? ? ? ? ? if(s.charAt(i)==s.charAt(j)){
? ? ? ? ? ? ? ? ? ? if(ishw(i,j,s)){
? ? ? ? ? ? ? ? ? ? ? ? temp=j-i+1;
? ? ? ? ? ? ? ? ? ? ? ? if(temp>ans){
? ? ? ? ? ? ? ? ? ? ? ? ? ? ans=temp;
? ? ? ? ? ? ? ? ? ? ? ? ? ? anss=s.substring(i,j+1);
? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return anss;
? ? }
? ? public boolean ishw(int i,int j,String s){
? ? ? ? if(i==j) return true;
? ? ? ? else if(j==i+1&&s.charAt(i)==s.charAt(j)) return true;
? ? ? ? else if(j==i+1&&s.charAt(i)!=s.charAt(j)) return false;
? ? ? ? else{
? ? ? ? ? ? if(s.charAt(i)==s.charAt(j)) return ishw(i+1,j-1,s);
? ? ? ? ? ? else return false;
? ? ? ? }
? ? }
}
方法二：只用了一重循環(huán)
思路是回文子序列必是AA或者ABA的形式
class Solution {
? ? public String longestPalindrome(String s) {
? ? ? ? int ans=0;
? ? ? ? if(s.length()==0) return s;
? ? ? ? if(s.length()==1) return s;
? ? ? ? int st=0;int end=0;
? ? ? ? for(int i=0;i<s.length();i++){
? ? ? ? ? ? int l1=hwnumbers(i,i,s);
? ? ? ? ? ? int l2=hwnumbers(i,i+1,s);
? ? ? ? ? ? if(l1>l2) ans=l1;
? ? ? ? ? ? else ans=l2;
? ? ? ? ? ? if(ans>end-st){
? ? ? ? ? ? ? ? st=i-(ans-1)/2;
? ? ? ? ? ? ? ? end=i+ans/2;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return s.substring(st, end + 1);
? ? }
? ? public int hwnumbers(int i,int j,String s){
? ? ? ? while(i>=0&&j<s.length()&&s.charAt(i)==s.charAt(j)) {
? ? ? ? ? ? i--;
? ? ? ? ? ? j++;
? ? ? ? }
? ? ? ? return j-i-1;
? ? }
}
