首页 > 代码库 > Longest Palindromic Substring

Longest Palindromic Substring

2024-07-10 04:43:37   212人阅读

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.

方法1 Dynamic programming 

定义一个二维数组记录是否是Palindromic。substring i to j is palindromic==>table[i][j]=1, else table[i][j]=0

base: table[i][i]=1;

table[i][i+1]=1 if s.charAt(i)==s.charAt(i+1);

When substring‘s length>=3:

table[i][j]=1 =>table[i+1][j-1]==1 && s.charAt(i)==s.charAt(j)

Time O(n^2) Space O(n^2)

public class Solution {    public String longestPalindrome(String s) {        if(s==null||s.length()<=1)            return s;        int max=0;//max length        int len=s.length();        int[][] table=new int[len][len];        String longestPalin="";                for(int i=0;i<len;i++){            table[i][i]=1;//every single char is palindromic            if(i==len-1){//length 2 need to stop here            break;            }            if(s.charAt(i)==s.charAt(i+1)){                table[i][i+1]=1;                max=2;                longestPalin=s.substring(i,i+2);            }        }                for(int l=3;l<=len;l++){            for(int i=0;i<=len-l;i++){ //be careful i<=len-1 e.g. l=3 len=3                int j=i+l-1;                if(s.charAt(i)==s.charAt(j)){                    table[i][j]=table[i+1][j-1];                    if(table[i][j]==1&&l>max){                        max=l;                        longestPalin=s.substring(i,j+1);                    }                }else{                    table[i][j]=0;                }            }        }        return longestPalin;    }}

方法二：

以每个char为中心和以每两个char之间为中心，向两边扩算寻找。

Time O(n^2) Space O(1)

注意最后一行，return s.substring(start+1,end)

input s,i,i 肯定进入循环，循环停止时，start多减了1，end多加了1，所以（start,end+1）变成(start+1,end)

input s,i,i+1, when s.charAt(i)!=s.charAt(i+1),不进入循环，strat+1=end, return ""。进入循环的同上。

public class Solution {    public String longestPalindrome(String s) {        if(s==null||s.length()<=1)            return s;        int max=0;//max length        int len=s.length();        String longestPalin="";        for(int i=0;i<len;i++){            //center is i            String sublen=longestPalindrome(s,i,i);            if(sublen.length()>max){               max=sublen.length();               longestPalin=sublen;            }                        //center is between i and i+1            if(i==len-1)                break;            sublen=longestPalindrome(s,i,i+1);            if(sublen.length()>max){               max=sublen.length();               longestPalin=sublen;            }        }             return longestPalin;    }        public String longestPalindrome(String s, int start, int end){         while(start>=0&&end<s.length()&&s.charAt(start)==s.charAt(end)){                start--;                end++;        }        return s.substring(start+1,end);    }}
 






























        

            
                
                  
                
                

                    联系

                    我们