# 5. Longest Palindromic Substring

## Description

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.


Example:

Input: "cbbd"

Output: "bb"


## code

class Solution {
public:
string longestPalindrome(string s) {
if(s.size()<2)
return s;
int max_len=1,max_left=0;
for(int mid=0;mid<s.size();){
int left=mid;
int right=mid;
while(right<s.size()-1&&s[left]==s[left+1])	++left;
mid=left+1;
while(right<s.size()-1&&left>0&&s[left-1]==s[right+1]){--left; ++right;}
int new_len=right-left+1;
if(new_len>max_len){max_left=left; max_len=new_len;}
}
return s.substr(max_left,max_len);
}
};


## 动态规划解法

• dp[i][j]==true为串s[i][j]为回文
• 将dp[i][i]，dp[i][i-1]初始化为true，其余全为false(即一个或两个字母组成的字符串均认为是回文)
• 之后穷举字串长度的值，对于其是否为回文，取决于 (s[i] == s[j] && dp[i+1][j-1] == true)

## code

/*Dynamic programming*/
class Solution {
public:
string longestPalindrome(string s) {
if(s.size()<2)
return s;
int max_len=1,max_left=0,s_len=s.size();
bool dp[s_len][s_len]={false};
dp[0][0]=true;
for(int i=1;i<s_len;++i){
dp[i][i]=true;
dp[i][i-1]=true;
}
for(int len=2;len<s_len;++len){
for(int i=0;i<=s_len-len;++i){
if(s[i]==s[i+len-1]&&dp[i+1][i+len-2]){
dp[i][i+len-1]=true;
if(len>max_len){
max_left=i;
max_len=len;
}
}
}
}
return s.substr(max_left,max_len);
}
};
`

### 学籍管理系统文档

#### 北邮教务系统评教脚本

Published on September 17, 2017

#### 72.Edit distance

Published on September 17, 2017