LeetCode Longest Palindromic Substring: DP vs Linear Approach

Overview

LeetCode Longest Palindromic Substring: Different DP formulas are given to tackle this problem and there even exists linear time approach.

LeetCode Longest Palindromic Substring

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.

Solution and Precautions: DP vs Linear Approach

(1) brute force: enumerate all the substrings O(N^2) and check each substring is palindromic or not O(N), so the total time is O(N^3)
(2) DP on palindromic property: F(i, j) = F(i+1, j – 1) if s[i] == s[j] if we define F(i, j) to be true or false indicating whether substring S[i]…S[j] is palindromic or not. So we still enumerate all the possible substrings O(N^2) by the order of increasing length  = 1 , 2, … N and check if the substring is palindromic or not in const time. So this apprach is O(N^2)
For this method, I provide my source code here in the following which is accepted by the leetcode OJ:
class Solution {
public:
    string gao(const std::string & strInput) {
        string strResult("");

    	if(strInput.size() == 0)
    	    return strResult;

    	bool isSymmentricString[1005][1005];
    	memset(isSymmentricString, 0, sizeof(isSymmentricString));

    	int iStringLength = strInput.size();
    	int iMaxStartIndex = 0;
    	int iMaxSymmtricStringLength = std::min(1, iStringLength);

    	for(int i = 0; i < iStringLength; ++i)
    		for(int j = i; j >= 0; --j)
    		isSymmentricString[i][j] = true;

    	for(int len = 2; len <= iStringLength; ++len) {
    		int iEndIndex = -1;
    		for(int iStartIndex = 0; iStartIndex + len <= iStringLength; ++ iStartIndex) {
    			iEndIndex = iStartIndex + len - 1;
    			if(strInput[iStartIndex] == strInput[iEndIndex] &&
    				isSymmentricString[iStartIndex + 1][iEndIndex - 1])	{
    					iMaxSymmtricStringLength = len;
    					iMaxStartIndex = iStartIndex;
    					isSymmentricString[iStartIndex][iEndIndex] = true;
    			}
    		}
    	}

    	return strInput.substr(iMaxStartIndex, iMaxSymmtricStringLength);
    }
    string longestPalindrome(string s) {
        return gao(s);
    }
};

Update on Feb 2, 2015, the following java code can pass the LeetCode OJ for this Longest Palindromic Substring as well:

public class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        if (n <= 1)
            return s;

        boolean [][] dp = new boolean[n][n];
        for (int i = 0; i < n; ++i)
            for (int j = i; j >= 0; --j)
                dp[i][j] = true;

        int maxLength = 1;
        int maxStart  = 0;
        for (int len = 2; len <= n; ++len) {
            for (int i = 0, j = i + len - 1; j < n; ++i, ++j) {
                if (s.charAt(i) == s.charAt(j) && dp[i+1][j-1]) {
                    dp[i][j] = true;
                    maxLength = len;
                    maxStart = i;
                }
                else
                    dp[i][j] = false;

            }
        }
        return s.substring(maxStart, maxStart + maxLength);
    }
}
(3) Longest common substring: by reversing S into S’ and find the longest common substring between S and S’, the longest substring must agree on the index between S and S’ to be the true longest Palindromic Substring in S.  We should pay special attention to this method, since a simple and careless implementation would lead to wrong answers, e.g., S = abcxdcba  S’ = abcdxcba, although we found the longest common substring is “abc” or “cba”, neither of these two agree on the index, no are they palindromic . One should think about this example for a bit before heading into this method.

LeetCode Longest Palindromic Substring, Tips and Divergent thinking:

(1) Be careful of the several points within the source code above, i.e., Firstly, the input might be empty string, that is why we test the size first.  Secondly, the initial condition for isSymmentricString[1005][1005] is to set all isSymmentricString[i][j] = true, where j <= i, it is not enough to set only isSymmentricString[i][i] = true. Thirdly, don’t try to copy the string into the final result string to return every time we got a longer palindromic substring, this copy takes O(N) time, which will leads to TLE from the OJ. So everytime we always record the start index and the length, rather than the potential longest palindromic substring.

(2) The three algorithm methods mentioned above for solving Longest Palindromic Substring problem are what I could come up with, there are some other quite thoughtful solutions including the linear time solution which could be found in the following links.

Very good references: “Longest Palindromic Substring Part I” and “Longest Palindromic Substring Part II

Summary

LeetCode Longest Palindromic Substring: Different DP formulas are given to tackle this problem and there even exists linear time approach.

Written on June 4, 2013