精选力扣500题第30题 LeetCode 5. 最长回文子串【c++ / java 详细题解】

清疚 2021-07-24 22:43 258阅读 0赞

### 目录 ###

*   *   *  1、题目
         *  2、思路
         *  3、c++代码
         *  4、java代码

### 1、题目 ###

给你一个字符串 `s`，找到 `s` 中最长的回文子串。

**示例 1：**

输入：s = "babad"
    输出："bab"
    解释："aba" 同样是符合题意的答案。

**示例 2：**

输入：s = "cbbd"
    输出："bb"

**示例 3：**

输入：s = "cbbd"
    输出："bb"
    示例 3：

**示例 4：**

输入：s = "ac"
    输出："a"

**提示：**

*  `1 <= s.length <= 1000`
 *  `s`仅由数字和英文字母（大写和/或小写）组成

### 2、思路 ###

**(双指针)**  O ( n 2 ) O(n^2) O(n2)

*  1、枚举数组中的每个位置`i`，从当前位置开始向两边扩散
 *  2、当回文子串是奇数时，从`i-1`,`i+1`开始往两边扩散
 *  3、当回文子串是偶数时，从`i`，`i + 1`开始往两边扩散
 *  4、找到以`i`为中心的最长回文子串的长度，若存在回文子串比以前的长，则更新回文串的最大长度，以及答案

**图示:**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]

### 3、c++代码 ###

class Solution { 
    public:
        string longestPalindrome(string s) { 
        string res;
        for(int i = 0; i < s.size(); i++)
         { 
             int l = i, r = i+1; //回文子串是偶数
             while( l >= 0 && r < s.size() && s[l] == s[r]) l--,r++;
             if( res.size() < r - l -  1) res = s.substr(l+1,r-l-1);
             l = i - 1, r = i + 1;//回文子串是奇数
             while( l >= 0 && r < s.size() && s[l] == s[r]) l--,r++;
             if( res.size() < r - l -  1) res = s.substr(l+1,r-l-1);
         }
        return res;
     }
    };

### 4、java代码 ###

class Solution { 
    
    
        public String longestPalindrome(String s) { 
    
            String res = "";
            for(int i = 0; i<s.length(); i++){ 
                //奇数情况
                int l = i - 1;
                int r = i + 1;
                while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)){ 
                    r ++;
                    l --;
                }
    
                // r-1 - (l+1) + 1 = r - l - 1
                if(res.length()<r-l-1) res=s.substring(l+1,r);
    
                //偶数情况
                l = i;
                r = i + 1;
                while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)){ 
                    r ++;
                    l --;
                }
    
                if(res.length()<r-l-1) res=s.substring(l+1,r);
    
            }
            return res;
        }
    }

**原题链接**：[5. 最长回文子串][5.]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]: /images/20210724/438b8513005848a8aee092385c3b4864.png
[5.]: https://leetcode-cn.com/problems/longest-palindromic-substring/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 1]: /images/20210724/09b0310603564d10809cfbf9c5331b05.png