# LeetCode题目：Longest Palindromic Substring，二维动态规划

By | 2012 年 9 月 30 日

Updated at 2016-04-28

# Question

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.

# Analyze

The brute force method will take O(n3) time, and apparently, it will exceed the time limit.

To reduce the time, as we noticed there are a lot of duplicated comparisons in the brute force method, the first thought is dynamic programming. But I was too aggressive at the begging, want to solve this with 1-D dynamic programming in O(n) time.

After find out several exceptional cases with either focus on the start of substring or the end of substring, I realized that it can not fit into a 1-D dynamic programming. But 2-D, can easily beat this question.

## 2-D Dynamic Programming

Let’s focus on the start index `si` and end index `ei` of the substring. When we want answer the question: “Is the substring s[si..ei] palindromic?”, we just check if s[si + 1 .. ei – 1] is palindromic and if s[si] == s[ei]. If both conditions are true, then we can get the positive answer. Then if we solve the problem in this order:

```for(int ei = 0; ei < s.length(); ei ++)
for(int si = ei; si >= 0; si --)
{ // implement here }
```

Then we can make sure when we resolve sub problem on (si, ei), we know the answer of (si+1, ei-1). So, just build a 2-D matrix and we can beat this question in O(n2) time.

## Expand from center

That’s the DP solution. And since it’s O(n2), then there is a more straight forward method with the same time level:
Just at each point in the string S, on the positions of it’s characters like 0,1,2,… or between characters like 0.5, 1.5, … . Then from this position, just expand the substring if it is still palindromic. Then there are O(n) centers and at each center, we need expand O(n) times. Thus, this is also a O(n2) time solution. And simpler.

# Codes

## Ruby version DP

```def longest_palindrome(s)
map = {}
max_si, max_ei, max_length = nil, nil, 0
s.length.times do |ei|
si = ei
while si >= 0 do
if si == ei
map[ei] = { si => true }
else
map[ei][si] = s[ei] == s[si] && (si + 1 >= ei || map[ei - 1][si + 1] == true)
end

len = (ei - si + 1)
if map[ei][si] && len > max_length
max_length = len
max_si = si
max_ei = ei
end

si -= 1
end
end

s[max_si..max_ei]
end
```

## Ruby version expand from center

```def expand(s, center)
li, ri = center.floor, center.ceil
if li == ri
li -= 1
ri += 1
end
left_space = li
right_space = s.length - ri - 1
max_space = [left_space, right_space].min
most_left = li - max_space
while li >= most_left do
if s[li] == s[ri]
li -= 1
ri += 1
else
break
end
end
#p [ri - li - 1, li + 1, ri - 1]
[ri - li - 1, li + 1, ri - 1]
end

def longest_palindrome(s)
i = 0
max_si, max_ei, max_len = nil, nil, 0
while i <= s.length - 1 do
len, si, ei = expand(s, i)
if max_len < len
max_si, max_ei, max_len = si, ei, len
end
i += 0.5
end
s[max_si..max_ei]
end
```

## C++ version DP

```class Solution {
public:
inline void setIsPalindrome(bool * dpmap, int si, int ei, int total_length, bool value) {
*(dpmap + total_length * ei + si) = value;
}
inline bool isPalindrome(bool * dpmap, int si, int ei, int total_length) {
return *(dpmap + total_length * ei + si);
}
string longestPalindrome(string s) {
int total_length = s.length();
int max_len = 0, max_si, max_ei;
bool *dpmap = new bool[total_length * total_length];
for(int ei = 0; ei < total_length; ei++) {
for(int si = ei; si >= 0; si--) {
bool positive =
(si == ei) ||
((s[si] == s[ei]) && ((si == ei - 1) || isPalindrome(dpmap, si + 1, ei - 1, total_length)));
setIsPalindrome(dpmap, si, ei, total_length, positive);
if(positive){
int len = ei - si + 1;
if(max_len < len){
max_len = len;
max_si = si;
max_ei = ei;
}
}
}
}
delete dpmap; dpmap = NULL;
return s.substr(max_si, max_len);
}
};
```

# 旧版，有误，奇怪的是当初竟然通过了测试…

1.在子函数longestCommonSub中，如果先new，在得到最长公共串之后delete申请的空间mat的话，运行到大概第5个test case的时候会报runtime error。
2.在代码段

`if(max <= len)`

```class Solution {
public:
string longestCommonSub(string &sa, string &sb) {
int rows = sa.size() + 1;
int cols = sb.size() + 1;
static int *mat = NULL;
if(NULL == mat) {
mat = new int[1001 * 1001];
}
for(int ir = 0 ; ir < rows; ++ ir) {
for(int ic = 0 ; ic < cols; ++ ic) {
*(mat + ir * cols + ic) = 0;
}
}
int max = 0;
int maxIr;
for(int ir = 1 ; ir < rows; ++ ir) {
char sai = sa[ir - 1];
for(int ic = 1 ; ic < cols; ++ ic) {
if(sai == sb[ic - 1]){
int len = 1 + *(mat + (ir-1) * cols + ic - 1);
*(mat + ir * cols + ic) = len;
if(max <= len) {
max = len;
maxIr = ir;
}
}
}
}
string result;
if(max > 0) {
result = sa.substr(maxIr - max, max);
}
return result;
}
string longestPalindrome(string s) {
string rs = s;
for( int i = 0 ; i < s.size(); ++ i) {
rs[i] = s[s.size() - 1 - i];
}
return longestCommonSub(s,rs);
}
};
```

## 2 thoughts on “LeetCode题目：Longest Palindromic Substring，二维动态规划”

1. blurjp

“寻找一个字符串中的最长可逆子串，可以转化为求它和自身的逆序串的最长公共子串问题。”这个假设是错的。

S = “abacdfgdcaba”, S’ = “abacdgfdcaba”.
The longest common substring between S and S’ is “abacd”. Clearly, this is not a valid palindrome.