longest palindrom

Dynamic programming solution, O(N2) time and O(N2) space: To improve over the brute force solution from a DP approach, first think how we can avoid unnecessary re-computation in validating palindromes. Consider the case “ababa”. If we already knew that “bab” is a palindrome, it is obvious that “ababa” must be a palindrome since the two left and right end letters are the same.

Stated more formally below:

Define P[ i, j ] ← true iff the substring Si … Sj is a palindrome, otherwise false.

Therefore,

P[ i, j ] ← ( P[ i+1, j-1 ] and Si = Sj )

The base cases are:

P[ i, i ] ← true P[ i, i+1 ] ← ( Si = Si+1 )

This yields a straight forward DP solution, which we first initialize the one and two letters palindromes, and work our way up finding all three letters palindromes, and so on…

This gives us a run time complexity of O(N2) and uses O(N2) space to store the table.

Note: the above from http://www.leetcode.com/2011/11/longest-palindromic-substring-part-i.html

public static string LongestPalindrom(string str)
        {
            if (str == null || str.Length < 2)
            {
                return str;
            }

            int longestIndex = -1;
            int maxLen = -1;
            bool[,] table = new bool[str.Length,str.Length];
            for (int i = 0; i < str.Length; i++)
            {
                table[i,i] = true;
                longestIndex = i;
                maxLen = 1;
            }

            for (int i = 0; i < str.Length - 1; i++)
            {
                if (str[i] == str[i + 1])
                {
                    table[i,i + 1] = true;
                    longestIndex = i;
                    maxLen = 2;
                }
            }

            for (int len = 3; len <= str.Length; len++)
            {
                for (int i = 0; i < str.Length - len + 1; i++)
                {
                    int j = i + len - 1;
                    if (str[i] == str[j] && table[i + 1,j-1])
                    {
                        table[i,j] = true;
                        longestIndex = i;
                        maxLen = len;
                    }
                }
            }

            return str.Substring(longestIndex, maxLen);
        }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s