LeetCode：5. Longest Palindromic Substring（找出一个字符串中最大的子回文串）

以你之姓@ 2022-04-08 08:15 160阅读 0赞

> **文章最前**： 我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。
> 
> 这博客是记录我学习的点点滴滴，如果您对 Python、Java、AI、算法有兴趣，可以关注我的动态，一起学习，共同进步。

**相关文章：**

1.  **[LeetCode：55. Jump Game（跳远比赛）][LeetCode_55. Jump Game]**
2.  **[Leetcode：300. Longest Increasing Subsequence（最大增长序列）][Leetcode_300. Longest Increasing Subsequence]**
3.  **[LeetCode：560. Subarray Sum Equals K（找出数组中连续子串和等于k）][LeetCode_560. Subarray Sum Equals K_k]**

--------------------

**文章目录：**

题目描述：

java实现方法1：

python实现方式1：

java实现方法2：

python实现方法2：

--------------------

### 题目描述： ###

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

示例 1：

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

示例 2：

输入: "cbbd"
    输出: "bb"

来源：力扣（LeetCode）

--------------------

### java实现方法1： ###

/**
         * 找出最大字符串
         *
         * @param s 最大字符串
         * @return 最大字符串
         */
        private static String longestPalindromicSubstring(String s) {
            String s1 = "";
            String s2 = "";
            for (int i = 0; i < s.length(); i++) {
                s1 = s1.length() >= maxSubStr(s, i, i).length() ? s1 : maxSubStr(s, i, i);
                s2 = s2.length() >= maxSubStr(s, i, i + 1).length() ? s2 : maxSubStr(s, i, i + 1);
            }
            return s1.length() >= s2.length() ? s1 : s2;
        }
    
        /**
         * @param s 字符串
         * @param i 位置i
         * @param j 位置j
         * @return 最大回文串
         */
        private static String maxSubStr(String s, int i, int j) {
            String maxString = "";
            while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
                String sub = s.substring(i, j + 1);
                if (sub.length() > maxString.length()) {
                    maxString = sub;
                }
                i--;
                j++;
            }
            return maxString;
        }

时间复杂度：O(n^2)

空间复杂度：O(n)

--------------------

### python实现方法1： ###

def get_longest_substr1(self, s: str) -> str:
            '''
                获取字符串中最大的子回文串
            Args:
                s: 字符串
            Returns:
                最长子字符串
            '''
            if len(s) <= 1:
                return s
            s1 = ''
            s2 = ''
            for i in range(len(s) - 1):
                # 字符串长度为基数
                if len(s1) < len(self.max_str(s, i, i)):
                    s1 = self.max_str(s, i, i)
                # 字符串长度为偶数时候
                if len(s2) < len(self.max_str(s, i, i + 1)):
                    s2 = self.max_str(s, i, i + 1)
            return s1 if len(s1) > len(s2) else s2
    
        def max_str(self, s: str, i: int, j: int) -> str:
            '''
                最大回文串
            Args:
                s: 总字符串
                i: 下标i
                j: 下标j
            Returns:
                最大子字符串
            '''
            while i >= 0 and j < len(s) and s[i] == s[j]:
                i -= 1
                j += 1
            return s[i + 1: j]

时间复杂度：O(n^2)

空间复杂度：O(n)

--------------------

### 源码地址： ###

[https://github.com/zhangyu345293721/leetcode][https_github.com_zhangyu345293721_leetcode]

[LeetCode_55. Jump Game]: https://blog.csdn.net/zy345293721/article/details/84991870
[Leetcode_300. Longest Increasing Subsequence]: https://blog.csdn.net/zy345293721/article/details/84984249
[LeetCode_560. Subarray Sum Equals K_k]: https://blog.csdn.net/zy345293721/article/details/84952201
[https_github.com_zhangyu345293721_leetcode]: https://github.com/zhangyu345293721/leetcode