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); } };

Hello There,

ReplyDeleteI 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