JAVA o(n*n). simple, not very fast


  • 1
    R
    public class Solution {
        public String longestPalindrome(String s) {
            int n = s.length(), longestBegin =0, maxLen =1;
            boolean dp[][] = new boolean[n][n];
            for(int i=0;i<n;i++)dp[i][i]=true;
            for(int i=0;i<n-1;i++){
                if(s.charAt(i) == s.charAt(i+1)){
                    dp[i][i+1]=true;
                    longestBegin = i;
                    maxLen = 2;
                }
            }
            for (int i=n-3; i >=0;i--){
                for(int j=i+1; j<n;j++){
                    if(s.charAt(i)==s.charAt(j)&&dp[i+1][j-1]){
                        dp[i][j]=true;
                        if(maxLen< j-i+1) {
                            longestBegin = i;
                            maxLen = j - i + 1;
                        }
                    }
                }
            }
            return s.substring(longestBegin,longestBegin+maxLen);
        }
    }

  • 0
    M
    public class Solution {
    public String longestPalindrome(String s) {
        int n = s.length(), longestBegin =0, maxLen =1;
        boolean dp[][] = new boolean[n][n];
    
        for(int i=0;i<n-1;i++){
            dp[i][i]=true; // cut previous for
            if(s.charAt(i) == s.charAt(i+1)){
                dp[i][i+1]=true;
                longestBegin = i;
                maxLen = 2;
            }
        }
    
        for (int i=n-3; i >=0;i--){
            for(int j=i+2; j<n;j++){ // start from i+2 works well
                if(s.charAt(i)==s.charAt(j)&&dp[i+1][j-1]){
                    dp[i][j]=true;
                    if(maxLen< j-i+1) {
                        longestBegin = i;
                        maxLen = j - i + 1;
                    }
                }
            }
        }
    
        return s.substring(longestBegin,longestBegin+maxLen);
    }
    

    }


  • 0

    could you get a AC?


  • 0
    This post is deleted!

  • 0
    // dp solution
    public class Solution {
        public String longestPalindrome(String s) {
            int len = s.length();
            int start = 0, max = 0;
        	boolean [][] dp = new boolean[len][len];
        	// dp
        	for ( int i = len - 1; i >= 0; i-- )
        	{
        		for ( int j = i; j <= len - 1; j++ )
        		{
        			if ( s.charAt( i ) == s.charAt( j ) )
        			{
        				if ( i + 1 > j - 1 )
        				{
        					dp[i][j] = true;
        				} else if ( dp[i + 1][j - 1] == true )
        				{
        					dp[i][j] = true;
        				}
        				if ( dp[i][j] == true &&  j - i + 1 > max )
        				{
        					start = i;
        					max = j - i + 1;
        				} 
        			}
        		}
        	}
        	return s.substring( start, start + max );
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.