# 5. 最长回文子串

<https://leetcode-cn.com/problems/longest-palindromic-substring/>

## 解法一：暴力

两个for循环，外层i遍历每个字符，然后内层j从i分别向两侧出发，找两头是否相等，不相等就退出循环。每次找到一个回文串，求长度，并记录首尾位置。

```python
class Solution {
public:
    string longestPalindrome(string s) {
        int maxLen = 0;
        int n = s.length();
        int start = 0, end = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; i-j >= 0 && i+j < n && s[i+j] == s[i-j]; j++) {  //回文长度为奇
                if (2*j+1 > maxLen) {  // len = (i+j)-(i-j)+1 = 2*j+1
                    start = i-j;
                    end = i+j;
                    maxLen = 2*j+1;
                }
            }
            for (int j = 0; i-1-j >= 0 && i+j < n && s[i-1-j] == s[i+j]; j++) {  //回文长度为偶
                if(2*j+2 > maxLen) {  // len = (i+j)-(i-1-j)+1 = 2*j+2
                    start = i-1-j;
                    end = i+j;
                    maxLen = 2*j+2;
                }
            }
        }
        return s.substr(start, end-start+1);
    }
};
```

```python
#python3:注意将c++中带复杂条件的for语句转换为py时，
#只能转成while语句来判断条件，在循环外设j初始值，在语句最后j自增
class Solution:
    def longestPalindrome(self, s: str) -> str:
        maxLen = 0
        n = len(s)
        start = 0
        end = 0
        for i in range(n):
            j = 0
            while i-j >= 0 and i+j < n and s[i+j] == s[i-j]:
                if 2*j+1 > maxLen:
                    start = i-j
                    end = i+j
                    maxLen = 2*j+1
                j += 1
            j = 0
            while i-1-j >= 0 and i+j < n and s[i-1-j] == s[i+j]:
                if 2*j+2 > maxLen:
                    start = i-1-j
                    end = i+j
                    maxLen = 2*j+2
                j += 1
        return s[start:end+1]
```

## 解法二：DP

`dp(i, j)` represents whether `s(i ... j)` can form a palindromic substring, `dp(i, j)` is true when s(i) equals to s(j) and `s(i+1 ... j-1)` is a palindromic substring. When we found a palindrome, check if it’s the longest one. Time complexity O(n^2). 需要注意的是构造初始解时，i是从n-1开始，为何？

看下图可知，对于串“aaaa”，由于`i<=j`，因此矩阵只有上三角。初始化斜对角全为1（因为单个字符必为回文串），第二条对角线根据是否有`i==j`决定（两个字符只有a==b才为回文）。其余每个元素`(i, j)`根据其左下方元素`(i+1, j-1)`决定。

![](/files/-M3ASWQHQ9Vq8EIrh29B)

```python
class Solution:
    def longestPalindrome(self, s: str) -> str:
        maxLen = 0
        n = len(s)
        res = ""
        dp = [[False] * n for _ in range(n)]  #二维数组创建
        for i in range(n-1, -1, -1):
            for j in range(i, n):
                if i == j:  #对角线
                    dp[i][j] = True
                elif j-i == 1:  #第二条对角线
                    dp[i][j] = s[i] == s[j]
                else:   #其余位置
                    dp[i][j] = dp[i+1][j-1] and s[i] == s[j]
                #找到更长的回文串
                if dp[i][j] and j-i+1 > maxLen:
                    maxLen = j-i+1
                    res = s[i:j+1]
        return res
```

实际上j由大到小也可以，因为填充方式是从下往上，因此只要保证i从大到小即可，j顺序可以随意，下一层都已经填完

```python
class Solution:
    def longestPalindrome(self, s: str) -> str:
        maxLen = 0
        n = len(s)
        res = ""
        dp = [[False] * n for _ in range(n)]  #二维数组创建
        for i in range(n-1, -1, -1):
            for j in range(n-1, i-1, -1):
                if i == j:  #对角线
                    dp[i][j] = True
                elif j-i == 1:  #第二条对角线
                    dp[i][j] = s[i] == s[j]
                else:   #其余位置
                    dp[i][j] = dp[i+1][j-1] and s[i] == s[j]
                #找到更长的回文串
                if dp[i][j] and j-i+1 > maxLen:
                    maxLen = j-i+1
                    res = s[i:j+1]
        return res
```

然而运行时dp比暴力慢许多，不知为何


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://cai-sen-se.gitbook.io/leetcode/1-200/5.-zui-chang-hui-wen-zi-chuan.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.