首页 > 代码库 > leetcode 5. Longest Palindromic Substring

leetcode 5. Longest Palindromic Substring

题目:找出字符串中最长的唯一回文串

两个解法:

一(O^n2):

分析:动态规划,flag[i][j]为true表示下标i,j之间的子串是回文串,保存上次的flag状态,判断此时下标为i,j的字符是否相等,得出此时的flag状态

代码:

public class Solution {
  public String longestPalindrome(String s) {
    int l=s.length();
    if(l<=1){
      return s;
    }
    boolean[][] flag=new boolean[l][l];
    int end=0,start=0,mas=0;
    for(int i=l-1;i>=0;i--){
    for(int j=i;j<l;j++){
      if(s.charAt(i)==s.charAt(j)&&(j-i<=2||flag[i+1][j-1])){

//下标为i,j的字符若相等,并且中间的子串是回文或者i与j之间小于等于2,则此时下标i,j之间的字符串为回文串

        flag[i][j]=true;//标记当前状态
        if(mas<j-i+1){//保存起始点,更新最大长度
          mas=j-i+1;
          start=i;
          end=j;
        }
      }
    }  
    }
    return s.substring(start,end+1);
  }
}

二(O^n):

 

leetcode 5. Longest Palindromic Substring