Share my concise thinking process with a special idea.


  • 0
    J

    ##Prerequisites: Longest common substring (LCS)

    For string a and b, their LCS is the longest common substring in both a and b.

    For example, for "abcda" and "bcea", the LCS is "bc".

    ##Solution

    Keeping LCS in mind, the longest palindromic substring of string s is, in fact, the LCS of s and its reversed string.

    For example, lets say s = "cabbad". Then its reversed string is s_rev = "dabbac".

    The LCS of s and s_rev is "abba", obviously. Note that this is also the longest padlindromic substring of s.

    Therefore, all we have to do is just finding the LCS of s and s.reverse(). This can be solved by DP.

    Take s1 = "cabbad" and s2 = "dabbac" as example. To find the LCS of s1 and s2, we use table[i][j] to denote the length of the LCS of s1.substring(i) and s2.substring(j).

    For example, table[4][4] = 3. Because s1.substring(4) is "cabb" and s2.substring(4) is "dabb", and the length of their LCS is len("abb") = 3.

    So, the math idea is simple:

    if	s1[i-1] != s2[j-1]	
    	table[i][j] = 0
    else
    	table[i+1][j+1]=table[i][j]+1
    

    (Note that table[i][j] should all be initialized to zero first.)

    Along with building the table[i][j], record the max length and its position (flag).

    When all the process is finished, the longest palindromic string is a.substring(flag-max_len, flag).

    Here's my Java code:

    public String longestPalindrome(String s) {
        StringBuilder rev = new StringBuilder(s);
        String s_rev = rev.reverse().toString();
        if(s_rev.equals(s))
        	return s;
        return longestCommonSubString(s, s_rev);
    }
    
    public String longestCommonSubString(String a, String b){
    	char[] sb1 = a.toCharArray(); 
    	char[] sb2 = b.toCharArray();
    	int[][] table = new int[a.length()+1][b.length()+1];
    	int flag = 0, max_len = 0;
    	for (int i = 1; i <= a.length(); i++) {
    		for (int j = 1; j <= b.length(); j++) {
    			if(sb1[i-1] == sb2[j-1]){
    				table[i][j] = table[i-1][j-1] + 1;
    				if(table[i][j] >= max_len){
    					max_len = table[i][j];
    					flag = i;
    				}
    			}
    		}
    	}
    	return a.substring(flag - max_len, flag);
    }
    

    In case of some extreme data like "aaaaa......aaaaa", I use the following code to avoid LTE.

        StringBuilder rev = new StringBuilder(s);
        String s_rev = rev.reverse().toString();
        if(s_rev.equals(s))
        	return s;
    

    Hope my sharing can help you :)


  • 1
    B

    @jiangyimin
    In case of "cltgaaaagtlc",your solution will be wrong. The reason is when the case is formed from a palindromic string which is separated by a normal string, there is a bug that the output is "cltg" instead of the true answer, "aaaa".


Log in to reply
 

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