LeetCode题目之腾讯精选练习（50题）：最长回文子串

朱雀 2024-04-17 16:36 82阅读 0赞

# 题目 #

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

**示例 1**:

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

**示例 2**:

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

## 算法实现 ##

public class Solution
    {
        
        public string LongestPalindrome(string s)
        {
        
            int start = 0;
            int longest = 0;
            int houbu = 0;
    
            //一个字母为中心
            for (int i = 0; i < s.Length; i++)
            {
        
                int left = i - 1;
                int right = i + 1;
                houbu ++;
                while (left >= 0 && right < s.Length && s[left] == s[right])
                {
        
                    houbu += 2;
                    left--;
                    right++;
                }
                if (houbu > longest)
                {
        
                    longest = houbu;
                    start = left + 1;
                }
                houbu = 0;
            }
    
            //两个字母为中心
            for (int i = 0; i < s.Length - 1; i++)
            {
        
                int left = i ;
                int right = i + 1;
                while (left >= 0 && right < s.Length && s[left] == s[right])
                {
        
                    houbu += 2;
                    left--;
                    right++;
                }
                if (houbu > longest)
                {
        
                    longest = houbu;
                    start = left + 1;
                }
                houbu = 0;
            }
                
            return s.Substring(start,longest);
        }
    }

## 执行结果 ##

**执行结果**：通过  
**执行用时** : 140 ms, 在所有 C\# 提交中击败了96.98%的用户  
**内存消耗** : 21.9 MB, 在所有 C\# 提交中击败了48.91%的用户  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]

## 小的总结 ##

这道题花了我很长时间，刚开始用暴力法，但是时间超出了限制，于是去看了官方的解答，了解了中心扩展法，但还是超时。之后看到群里用Substring函数，才将我点醒：不需要每次记录回文子串，只需记录其在字符串中的位置和长度，这样大大节省了时间和空间，真是受益匪浅。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/08597a0d87ee41a991eee59b1754e4da.png