5. 最长回文子串(Longest Palindromic Substring)M

英文题目

Given a string s, return the longest palindromic substring in s.
Example 1:

Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:
```
Input: s = "cbbd"
Output: "bb"
```
Example 3:
```
Input: s = "a"
Output: "a"
```
Example 4:
```
Input: s = "ac"
Output: "a"
```
Constraints:
1 <= s.length <= 1000
s consist of only digits and English letters (lower-case and/or upper-case),

中文题目

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：
```
输入: "cbbd"
输出: "bb"
```

暴力解法

遍历所有的子串，判断是否是回文

时间复杂度O(n^3)，空间复杂度O(1)

# 超时
class Solution:
    def longestPalindrome(self, s: str) -> str:
        max_len, res = 0, ""
        for start in range(len(s)):
            # 注意python的字符是左闭右开
            for end in range(start+1, len(s)+1):
                if self.is_palindrome(s[start:end]) and end - start > max_len:
                    res = s[start:end]
                    max_len = end - start
        return res
    
    def is_palindrome(self, s: str):
        start, end = 0, len(s) - 1
        while start < end:
            if s[start] != s[end]:
                return False
            start, end = start + 1, end - 1
        return True

动态规划

令dp[i][j]表示S[i]到S[j]所表示的子串是否是回文子串，是为True，不是为False
有两种情况：
1.若S[i]==S[j]，那么只要S[i+1]到S[j-1]是回文子串，S[i]到S[j]就是回文子串
2.若S[i]!=S[j]，那么S[i]到S[j]一定不是回文子串
状态转移方程：
边界：dp[i][i]=1, dp[i][i+1]=(S[i]==S[i+1])?True:False（边界即为长度为1和2的子串）
枚举方式应该是按照子串的长度和子串的初始位置进行枚举

时间复杂度为O(n^2)，空间复杂度O(n^2)

# python3: 时间 4248 ms, 击败 32.90%; 内存 23.8 MB, 击败 25.44%
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n < 2:
             return s
        
        maxLen = 1
        begin = 0
        # dp[i][j] 表示 s[i..j] 是否是回文串
        dp = [[False] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = True

        # 先枚举子串长度
        for length in range(2, n+1):
            # 枚举左边界，左边界的上限设置可以宽松
            for left in range(n):
                # 由 length 和 left 可以确定右边界，
                # 即 right - left + 1 = length 得
                right = left + length - 1
                # 如果右边界越界，就可退出当前循环
                if right >= n:
                    break

                if s[left] != s[right]:
                    dp[left][right] = False
                else:
                    # 此处判断是为了字符串长度为 2 
                    if right - left == 1:
                        dp[left][right] = True
                    else:
                        dp[left][right] = dp[left+1][right-1]

                # 只要 dp[i][L] == true 成立，就表示子串 s[i..L]
                # 是回文，此时记录回文长度和起始位置
                if dp[left][right] and length > maxLen:
                    maxLen = length
                    begin = left
        return s[begin:begin+maxLen]

// c++: 时间 396 ms, 击败 22.92%; 内存 22.2 MB, 击败 46.69%
class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if (n < 2) {
            return s;
        }

        vector<vector<bool>> dp(n, vector<bool>(n, false));
        int maxLen = 1;
        int begin = 0;
        for (int i = 0; i < n; ++i) {
            dp[i][i] = true;
        }

        for (int length = 2; length <= n; ++length) {
            for (int left = 0; left < n; ++left) {
                int right = left + length - 1;
                if (right >= n) {
                    break;
                }

                if (s[left] != s[right]) {
                    dp[left][right] = false;
                } else {
                    if (right - left == 1) {
                        dp[left][right] = true;
                    } else {
                        dp[left][right] = dp[left+1][right-1];
                    }
                }

                if (dp[left][right] && length > maxLen) {
                    maxLen = length;
                    begin = left;
                }
            }
        }
        return s.substr(begin, maxLen);
    }
};

// java: 时间 171 ms, 击败 19.48%; 内存 45 MB, 击败 10.27%
class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        if (n < 2) {
            return s;
        }
        
        int maxLen = 1;
        int begin = 0;
        boolean[][] dp = new boolean[n][n];
        for (int i = 0; i < n; ++i) {
            dp[i][i]= true;
        }

        for (int length = 2; length <= n; ++length) {
            for (int left = 0; left < n; ++left) {
                int right = left + length - 1;
                if (right >= n) {
                    break;
                }

                if (s.charAt(left) != s.charAt(right)) {
                    dp[left][right] = false;
                } else {
                    if (right - left == 1) {
                        dp[left][right] = true;
                    } else {
                        dp[left][right] = dp[left+1][right-1];
                    }
                }

                if (dp[left][right] && length > maxLen) {
                    maxLen = length;
                    begin = left;
                }
            }
        }
        return s.substring(begin, begin+maxLen);
    }
}

// go: 时间 68 ms, 击败 29%; 内存 7.2 MB, 击败 33.75%
func longestPalindrome(s string) string {
    n := len(s)
    if n < 2 {
        return s
    }

    maxLen := 1
    begin := 0
    dp := make([][]bool, n)
    for i := 0; i < n; i++ {
        dp[i] = make([]bool, n)
        dp[i][i] = true
    }

    for length := 2; length <= n; length++ {
        for left := 0; left < n; left++ {
            right := left + length - 1
            if right >= n {
                break
            }

            if s[left] != s[right] {
                dp[left][right] = false
            } else {
                if right - left == 1 {
                    dp[left][right] = true
                } else {
                    dp[left][right] = dp[left+1][right-1]
                }
            }

            if dp[left][right] && length > maxLen {
                maxLen = length
                begin = left
            }
        }
    }
    return s[begin:begin+maxLen]
}

// javascript: 时间 824 ms, 击败 14.76%; 内存 69 MB, 击败 21.47%
/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let n = s.length;
    if (n < 2) {
        return s;
    }

    let maxLen = 1;
    let begin = 0;
    const dp = new Array(n);
    for (let i = 0; i < n; ++i) {
        dp[i] = new Array(n).fill(false);
        dp[i][i] = true;
    }

    for (let length = 2; length <= n; ++length) {
        for (let left = 0; left < n; ++left) {
            let right = left + length - 1;
            if (right >= n) {
                break;
            }

            if (s.charAt(left) != s.charAt(right)) {
                dp[left][right] = false;
            } else {
                if (right - left == 1) {
                    dp[left][right] = true;
                } else {
                    dp[left][right] = dp[left+1][right-1];
                }
            }
            if (dp[left][right] && length > maxLen) {
                maxLen = length;
                begin = left;
            }
        }
    }
    return s.substring(begin, begin+maxLen);
};

中心扩散

枚举所有的「回文中心」并尝试「扩展」，直到无法扩展为止，此时的回文串长度即为次「回文中心」下的最长回文串长度

时间复杂度O(n^2)，空间复杂度O(1)

# python3: 时间 544 ms, 击败 64.14%; 内存 16 MB, 击败 77.84%
class Solution:
    def longestPalindrome(self, s: str) -> str:
        res = ""
        for i in range(len(s)):
            res1 = self.expandAroundCenter(s, i, i)
            res2 = self.expandAroundCenter(s, i, i+1)
            res = res1 if len(res) < len(res1) else res
            res = res2 if len(res) < len(res2) else res
        return res
    
    def expandAroundCenter(self, s: str, l: int, r: int) -> str:
        while 0 <= l and r < len(s) and s[l] == s[r]:
            l, r = l-1, r+1
        return s[l+1:r]

// c++: 时间 52 ms, 击败 65.79%; 内存 164.9 MB, 击败 27.51%
class Solution {
public:
    string longestPalindrome(string s) {
        string res = "";
        for (int i = 0; i < s.size(); ++i) {
            string res1 = expandAroundCenter(s, i, i);
            string res2 = expandAroundCenter(s, i, i+1);
            res = res.size() < res1.size() ? res1 : res;
            res = res.size() < res2.size() ? res2 : res;
        }
        return res;
    }

    string expandAroundCenter(string s, int l, int r) {
        while (0 <= l && r < s.size() && s[l] == s[r]) {
            --l;
            ++r;
        }
        return s.substr(l+1, r-l-1);
    }
};

// java: 时间 20 ms, 击败 72.66%; 内存 43.3 MB, 击败 44.71%
class Solution {
    public String longestPalindrome(String s) {
        String res = "";
        for (int i = 0; i < s.length(); ++i) {
            String res1 = expandAroundCenter(s, i, i);
            String res2 = expandAroundCenter(s, i, i+1);
            res = res.length() < res1.length() ? res1 : res;
            res = res.length() < res2.length() ? res2 : res; 
        }
        return res;
    }

    private String expandAroundCenter(String s, int l, int r) {
        while (0 <= l && r < s.length() && s.charAt(l) == s.charAt(r)) {
            --l; 
            ++r;
        }
        return s.substring(l+1, r);
    }
}

// go: 时间 0 ms, 击败 100%; 内存 2.3 MB, 击败 99.74%
func longestPalindrome(s string) string {
    res := ""
    for i := 0; i < len(s); i++ {
        res1 := expandAroundCenter(s, i, i)
        res2 := expandAroundCenter(s, i, i+1)
        if len(res1) > len(res) {
            res = res1
        }
        if len(res2) > len(res) {
            res = res2
        }
    }
    return res
}

func expandAroundCenter(s string, l, r int) string {
    for 0 <= l && r < len(s) && s[l] == s[r] {
        l--;
        r++;
    }
    return s[l+1:r]
}

// javascript: 时间 72 ms, 击败 94.73%; 内存 43.8 MB, 击败 58.37%
/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let res = "";
    for (let i = 0; i < s.length; ++i) {
        let res1 = expandAroundCenter(s, i, i);
        let res2 = expandAroundCenter(s, i, i+1);
        res = res.length < res1.length ? res1 : res;
        res = res.length < res2.length ? res2 : res;
    }
    return res;
};

let expandAroundCenter = function(s, l, r) {
    while (0 <= l && r < s.length && s.charAt(l) == s.charAt(r)) {
        --l;
        ++r;
    }
    return s.substring(l+1, r);
}

# 5. 最长回文子串(Longest Palindromic Substring)M

# 英文题目

# 中文题目

# 暴力解法

# 动态规划

# 中心扩散

5. 最长回文子串(Longest Palindromic Substring)M

英文题目

中文题目

暴力解法

动态规划

中心扩散