O(n^2) solution TTL


  • 0
    D

    import java.util.*;
    public class Solution {
    public String longestPalindrome(String s) {
    StringBuffer sb = new StringBuffer(s);
    return longestCommonStr(s.toString(),sb.reverse().toString());
    }

    public String longestCommonStr(String s1,String s2)
    { 
        int st=-1;
        int e = -1;
        int len = 0;
        int max = 0;
        int store[][] = new int[s1.length()+1][s2.length()+1];
        int ans[][] = new int[s1.length()+1][s2.length()+1];
        for(int i=0;i<store.length;i++)
        {
            store[i][0] = 0;
            store[0][i] = 0;
            ans[i][0] = -1;
            ans[0][i] = -1;
        }
        for(int i=1;i<store.length;i++)
        for(int j=1;j<store.length;j++)
        {
            store[i][j]  =   0;
            if(s1.charAt(i-1)==s2.charAt(j-1))
            {
                store[i][j]= store[i-1][j-1] +1;
                if(store[i-1][j-1] == 0)
                ans[i][j] = i-1;
                else 
                ans[i][j] = ans[i-1][j-1];
                   
            }
            if(store[i][j]>max && s1.substring(ans[i][j],i).
                          equals(s2.substring(s2.length()-(i-1)-1,
                                              s2.length()-ans[i][j]-1+1))) 
            { 
                e = i-1;
                st = ans[i][j];
                max = store[i][j];
                
            }
        }
        return s1.substring(st,e+1);
    }
    

    }


Log in to reply
 

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