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.

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 {
    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++){
        for (int i=0;i<n-1;i++){
            if (s[i]==s[i+1]){
        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]){
        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,