leetcode Question 44: Longest Palindromic Substring

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.


Analysis:
This is a DP problem. According to http://leetcode.com/2011/11/longest-palindromic-substring-part-i.html
table[i][j] saves if the string start from i ends at j is the Palindromic string.

Initial state:
table[i][i] =  true.
table[i][i+1] = (s[i]==s[i+1]);

State Change:
if s[i]==s[j], table[i][j]=table[i+1][j-1];


Source Code:

class Solution {
public:
    string longestPalindrome(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int n=s.size();
        if(n==0){return "";}
        
        // Using vector might NOT pass the large test, use array instead.
        //vector<vector<bool> > table(n,vector<bool>(n,false));
        
        bool table[1000][1000] = {false};
        
        int maxst=0;
        int maxlen=1;
         
        for (int i=0;i<n;i++){
            table[i][i]=true; 
            maxst=i;
            maxlen=1;
        }
        for (int i=0;i<n-1;i++){
            if (s[i]==s[i+1]){
                table[i][i+1]=true;
                maxst=i;
                maxlen=2;
            }
        }
         
        for (int len=3; len<=n;len++){
            for (int i=0;i<n-len+1;i++){
                int j=i+len-1;
                if (s[i]==s[j] && table[i+1][j-1]){
                    table[i][j]=true;
                    maxst=i;
                    maxlen=len;
                }
            }
        }
        return s.substr(maxst,maxlen);
    }
};

1 comment:

  1. Hello There,


    I am shocked, shocked, that there is such article exist!! But I really think you did a great job highlighting some of the key Job Yu's Coding Garden in the entire space.

    I need to use 2 dimensional array in my project.
    I need to bring the Output in this format

    Eg i[0]j[0] i[1]j[1], i[2]j[2] using for each loop . My array size is 6 I[6] j[6] both are integers .It first go and calculate the I th value i=0 and then it come to J th for loop and calculate the J=0 . then it again go to i[1] and j[1] .. Please any one tell me the program for this kind of looping.

    I am so grateful for your blog. Really looking forward to read more.


    Many Thanks,
    Teena

    ReplyDelete