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

题目

给定一个字符串 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%的用户

小的总结

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