大家好，我是编程熊，今天是LeetCode每日一题的第五天，一起学习LeetCode第五题《最长回文子串》。
题意
给你一个字符串 s，找到 s 中最长的回文子串。
示例
1输入：s = "babad" 2输出："bab" 3解释："aba" 同样是符合题意的答案。
题解
方法一
采用简单暴力的方法，枚举每一个位置为单独回文中心(长度为奇数的子串，如 aba)或者回文中心中的一个(长度为偶数的子串，如abba)，同时向左和向右扩展查看是否相等，直至 不相等 或 到字符串开头/结尾 停止扩展。最坏的情况下，如 aaaaaa ，时间复杂度为 $O(n^2)$。
1// C++代码 2class Solution { 3public: 4 string longestPalindrome(string s) { 5 int st = 0, ed = 0; 6 for (int i = 0; i < s.size(); i++) { 7 auto ans1 = expandMaxLen(s, i, i); 8 auto ans2 = expandMaxLen(s, i, i + 1); 9 if (ans1.second - ans1.first > ed - st) { 10 ed = ans1.second; 11 st = ans1.first; 12 } 13 if (ans2.second - ans2.first > ed - st) { 14 ed = ans2.second; 15 st = ans2.first; 16 } 17 } 18 return s.substr(st, ed - st + 1); 19 } 20 pair<int, int> expandMaxLen(string s, int l, int r) { 21 while (l >= 0 && r < s.size() && s[l] == s[r]) { 22 --l; 23 ++r; 24 } 25 pair<int, int> ans = {l + 1, r - 1}; 26 return ans; 27 } 28};
时间复杂度: $O(n^2)$
空间复杂度: $O(n)$
方法二
Manacher算法 可以在 $O(n)$ 的时间复杂度下，求字符串的最长回文子串，后续会专门出一篇文章讲解 Manacher算法。
下面代码给的是 Manacher算法 解决的，代码超过了99.9%的解法，大家可以先理解一下。
时间复杂度: $O(n)$
空间复杂度: $O(n)$
知识点总结: 枚举、Manacher算法。
C++代码
1class Solution { 2public: 3 string longestPalindrome(string s) { 4 string str = preSovle(s); 5 int max_id = 0, max_pos = 0, ans_pos, ans_len = 0; 6 vector<int> arm_len(str.size(), 0); 7 for (int i = 2; i <= str.size() - 2; i++) { 8 if (max_pos > i) arm_len[i] = min(max_pos - i, arm_len[2 * max_id - i]); 9 else arm_len[i] = 1; 10 while (str[i + arm_len[i]] == str[i - arm_len[i]]) arm_len[i]++; 11 if (i + arm_len[i] > max_pos) { 12 max_pos = i + arm_len[i]; 13 max_id = i; 14 } 15 if (arm_len[i] - 1 > ans_len) { 16 ans_len = arm_len[i] - 1; 17 ans_pos = i; 18 } 19 } 20 int pos = (ans_pos - 2) / 2; 21 return str[ans_pos] == '#' ? s.substr(pos - ans_len / 2 + 1, ans_len): 22 s.substr(pos - ans_len / 2, ans_len); 23 } 24 string preSovle(string s) { 25 string str = "$"; 26 for (int i = 0; i < s.size(); i++) { 27 str += '#'; 28 str += s[i]; 29 } 30 str += '#', str += '*'; 31 return str; 32 } 33};
Java代码
1class Solution { 2 public String longestPalindrome(String s) { 3 String str = preSolve(s); 4 int max_id = 0, max_pos = 0, ans_pos = 0, ans_len = 0; 5 int[] arm_len = new int[str.length()]; 6 7 for (int i = 2; i <= str.length() - 2; i++) { 8 if (max_pos > i) arm_len[i] = Math.min(max_pos - i, arm_len[2 * max_id - i]); 9 else arm_len[i] = 1; 10 while (str.charAt(i + arm_len[i]) == str.charAt(i - arm_len[i])) arm_len[i]++; 11 if (i + arm_len[i] > max_pos) { 12 max_pos = i + arm_len[i]; 13 max_id = i; 14 } 15 if (arm_len[i] - 1 > ans_len) { 16 ans_len = arm_len[i] - 1; 17 ans_pos = i; 18 } 19 } 20 int pos = (ans_pos - 2) / 2; 21 return str.charAt(ans_pos) == '#' ? s.substring(pos - ans_len / 2 + 1, pos - ans_len / 2 + ans_len + 1): 22 s.substring(pos - ans_len / 2, pos - ans_len / 2 + ans_len); 23 } 24 25 public String preSolve(String s) { 26 String str = "$"; 27 for (int i = 0; i < s.length(); i++) { 28 str = str.concat("#"); 29 str += s.charAt(i); 30 } 31 str += '#'; 32 str += '*'; 33 return str; 34 } 35}
题目链接: https://leetcode-cn.com/problems/longest-palindromic-substring/
我是编程熊，持续输出 LeetCode题解、大厂面试、大厂靠谱点对点内推 相关内容，公众号关注''一只编程熊"，获取信息吧！
欢迎 『关注』、『点赞』、『转发』支持~