本文共 3842 字，大约阅读时间需要 12 分钟。

为了找到字符串s中的最长回文子串，我们可以采用中心扩展法。这种方法通过将每个字符作为中心，向两边扩展，检查是否能形成回文。这种方法的时间复杂度是O(n²)，能够高效处理长度较大的字符串。

方法思路

解决代码

        
   
        
    
文章目录
        
    
            
     
                
      
                    
       
                    
       
                    
       
                    
       
                    
       
                    
       
                
      
            
        
    
    
   
    
   
        
    
题目
        
    
给定一个字符串 s，找到 s 中最长的回文子串。
                
    
            
     
示例 1：
            
     
输入: “babad”
            
     
输出: “bab”
            
     
注意: “aba” 也是一个有效答案。
        
    
        
    
            
     
示例 2：
            
     
输入: “cbbd”
            
     
输出: “bb”
        
    
        
    
        
    
解法一（暴力法）
        
    
思路：原理就是对字符串从前到后依次进行遍历，最外层循环为子串头，第二层循环为确定子串尾，第三层循环为确定子串是否满足回文约束。
        
    
            
     
时间复杂度：O(n³)
            
     
空间复杂度：O(1)
        
    
        
    
        
    
解法二（中心扩展）
        
    
思路：把每个字符作为回文串的中心点，向两边扩展进行检测来确定当前字符为中心的回文串长度，所有子串的最大长度即为所求。
        
    
            
     
时间复杂度：O(n²)
            
     
空间复杂度：O(1)
        
    
        
    
        
    
解法三（动态规划）
        
    
思路：可以当做基于暴力解法的一种优化，将已经得到的回文串保存起来，用于求解新的回文串。对于一个回文子串，如果两边的字母一样，则可以分别向两边扩展一步形成新的回文串，如果两边字母不同，那当前串即为最长回文子串，直到找到最长的字符。
        
    
            
     
时间复杂度：O(n²)
            
     
空间复杂度：O(n²)
        
    
        
    
        
    
优化方案
        
    
由于暴力法的时间复杂度太高，尤其是对于长度较大的字符串会超时，因此选择中心扩展法作为优化方案。这种方法的时间复杂度为O(n²)，能够高效处理较大的字符串。
        
    
            
     
最终解法
            
     
采用中心扩展法，代码如下：
            ```java            public class Solution {                public string LongestPalindrome(string s) {                    int max_length = -1;                    int start = 0;                    int end = 0;                    int n = s.Length;                    for (int i = 0; i < n; i++) {                        // 检查以i为中心的奇数长度回文                        int l = i - 1;                        int r = i + 1;                        while (l >= 0 && r < n && s[l] == s[r]) {                            l--;                            r++;                        }                        int current_length = r - l - 1;                        if (current_length > max_length) {                            max_length = current_length;                            start = l + 1;                            end = r - 1;                        }                        // 检查以i为中心的偶数长度回文                        l = i;                        r = i + 1;                        while (l >= 0 && r < n && s[l] == s[r]) {                            l--;                            r++;                        }                        current_length = r - l - 1;                        if (current_length > max_length) {                            max_length = current_length;                            start = l + 1;                            end = r - 1;                        }                    }                    if (max_length == -1) {                        return "";                    } else {                        return s.Substring(start, max_length + 1);                    }                }            }            ```            
     
代码解释：
            
     
                
      
初始化max_length为-1，表示最长回文子串的长度初始为0。
                
      
遍历每个字符i，分别处理奇数长度和偶数长度的回文。
                
      
对于奇数长度，检查字符i两边的字符是否相同，向外扩展直到字符不相同。
                
      
对于偶数长度，检查字符i和i+1两边的字符是否相同，向外扩展直到字符不相同。
                
      
记录最长回文子串的位置和长度，最后返回结果。
            
     
        
    
    
   

代码解释

• 初始化变量：max_length 记录最长回文子串的长度，start 和 end 记录子串的起始和结束位置。
• 遍历每个字符：外层循环遍历每个字符，分别处理奇数和偶数长度的回文。
• 扩展检查：对于每个中心，向两边扩展，检查左右字符是否相同。
• 更新最大值：如果当前回文子串更长，则更新最大值。
• 返回结果：根据记录的位置和长度生成最长回文子串。

这种方法在时间复杂度和空间复杂度上都优于暴力法，能够高效解决问题。