## Monday, December 24, 2012

### [LeetCode] 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.
» Solve this problem

[解题思路]
O(n*n)。对于每一个字符，以之作为中间元素往左右寻找。注意处理奇偶两种模式：
1. aba
2. abba

``````1:  string longestPalindrome(string s) {
2:      // Start typing your C/C++ solution below
3:      // DO NOT write int main() function
4:      int startIndex = 0;
5:      int len = 0;
6:      int sI,eI;
7:      for(int i =0; i< s.size() -1; i++)
8:      {
9:           if(s[i] == s[i+1])
10:          {
11:               sI = i;
12:               eI = i+1;
13:               Search(s, sI, eI, len, startIndex);
14:          }
15:          sI = i;
16:          eI = i;
17:          Search(s, sI, eI, len, startIndex);
18:      }
19:      if(len == 0)
20:        len = s.size();
21:      return s.substr(startIndex, len);
22:    }
23:    void Search(string&s, int sI, int eI, int&len, int& startIndex)
24:    {
25:      int step = 1;
26:      while((sI-step)>=0&& (eI+step)<s.size())
27:      {
28:        if(s[sI-step] != s[eI+step])
29:        {
30:          break;
31:        }
32:        step++;
33:      }
34:      int wid = eI- sI+2*step -1;
35:      if(wid > len)
36:      {
37:        len = wid;
38:        startIndex = sI - step+1;
39:      }
40:    }
``````

P[i,j] = 字符串区间[i,j]是否为palindrome.

S=    a  b  c  c  b
Index = 0  1  2  3  4

P[0,0] =1  //each char is a palindrome
P[0,1] =S[0] == S[1]    , P[1,1] =1
P[0,2] = S[0] == S[2] && P[1,1], P[1,2] = S[1] == S[2] , P[2,2] = 1
P[0,3] = S[0] == S[3] && P[1,2], P[1,3] = S[1] == S[3] && P[2,2] , P[2,3] =S[2] ==S[3],  P[3,3]=1
......................

P[i,j] = 1  if i ==j
=  S[i] ==S[j]   if j = i+1
=  S[i] == S[j] && P[i+1][j-1]  if j>i+1

``````1:       string longestPalindrome(string s) {
2:            int len = s.size();
3:            int P[len][len];
4:            memset(P, 0, len*len*sizeof(int));
5:            int maxL=0, start=0, end=0;
6:            for(int i =0; i< s.size(); i++)
7:            {
8:                 for(int j =0; j<i; j++)
9:                 {
10:                      P[j][i] = (s[j] == s[i] && (i-j<2 || P[j+1][i-1]));
11:                      if(P[j][i] && maxL < (i-j+1))
12:                      {
13:                           maxL = i-j+1;
14:                           start = j;
15:                           end = i;
16:                      }
17:                 }
18:                 P[i][i] =1;
19:            }
20:            return s.substr(start, end-start +1);
21:       }
``````