LeetCode题目之腾讯精选练习(50题):最长回文子串 朱雀 2024-04-17 16:36 22阅读 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
还没有评论,来说两句吧...