### 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