【算法】5. 最长回文子串（多语言实现）
【摘要】 给你一个字符串 s，找到 s 中最长的回文子串。
5. 最长回文子串：
给你一个字符串 s，找到 s 中最长的回文子串。
样例 1：
输入：
s = "babad"
输出：
"bab"
解释：
"aba" 同样是符合题意的答案。
样例 2：
输入：
s = "cbbd"
输出：
"bb"
样例 3：
输入：
s = "a"
输出：
"a"
样例 4：
输入：
s = "ac"
输出：
"a"
提示：
- 1 <= s.length <= 1000
- s 仅由数字和英文字母（大写 和 / 或 小写）组成
分析：
- 面对这道算法题目，二当家的陷入了沉思。
- 判断回文，一般就是双指针从两侧向中心移动判断。
- 但是这里如果还是用这种方式效率就会很低。
- 可以考虑判断每个字符作为中心时候，双指针向两侧移动，直到字符不同，就是该字符作为中心的最长回文。
- 另外对于长的回文，在其右臂的字符上找回文子串时可以利用左臂缓存加速，因为右臂与左臂对称。
题解：
rust
impl Solution {
pub fn longest_palindrome(s: String) -> String {
fn expand(s: &Vec<char>, left: usize, mut right: usize) -> usize {
// 强转了i32是为了可以出负数
let mut left = left as i32;
while left >= 0 && right < s.len() && s[left as usize] == s[right] {
left -= 1;
right += 1;
}
return ((right as i32 - left - 2) >> 1) as usize;
}
let mut ns = Vec::with_capacity((s.len() << 1) + 1);
ns.push('#');
s.chars().for_each(|x| {
ns.push(x);
ns.push('#');
});
// 最终结果的头尾下标
let (mut start, mut end) = (0, 0);
// 臂长缓存
let mut arm_len = vec![0usize; ns.len()];
// 之前回文串的右边界,之前回文串的中位下标
let (mut right, mut mid) = (0, 0);
for i in 0..ns.len() {
// 判断是否有过臂长缓存
let min_arm_len;
if i < right {
// 缓存范围内
min_arm_len = arm_len[(mid << 1) - i].min(right - i);
} else {
min_arm_len = 0;
}
// 当前臂长
let cur_arm_len = expand(&ns, i - min_arm_len, i + min_arm_len);
// 将当前臂长缓存
arm_len[i] = cur_arm_len;
// 新的串超出之前子串的范围，用新的范围覆盖
if i + cur_arm_len > right {
mid = i;
right = i + cur_arm_len;
}
// 当前结果大于之前的结果
if (cur_arm_len << 1) + 1 > end - start {
start = i - cur_arm_len;
end = i + cur_arm_len;
}
// 如果后面的剩下的字符不够最大臂长就没必要进行下去了
if i + ((end - start) >> 1) >= ns.len() {
break;
}
}
return String::from(&s[start >> 1..end >> 1]);
}
}
go
func longestPalindrome(s string) string {
min := func(a int, b int) int {
if a < b {
return a
}
return b
}
expand := func(s []uint8, left int, right int) int {
for left >= 0 && right < len(s) && s[left] == s[right] {
left--
right++
}
return (right - left - 2) >> 1
}
// 在字符之间加入#号，使得字符数恒定变为奇数
ns := make([]uint8, len(s)<<1+1)
ns[0] = '#'
for i := 0; i < len(s); i++ {
ns[(i<<1)+1] = s[i]
ns[(i+1)<<1] = '#'
}
// 最终结果的头尾下标
start, end := 0, 0
// 臂长缓存
armLen := make([]int, len(ns))
// 之前回文串的右边界,之前回文串的中位下标
right, mid := 0, 0
for i := 0; i < len(ns); i++ {
// 判断是否有过臂长缓存
var minArmLen int
if right > i {
minArmLen = min(armLen[(mid<<1)-i], right-i)
} else {
minArmLen = 0
}
// 当前臂长
curArmLen := expand(ns, i-minArmLen, i+minArmLen)
// 将当前臂长缓存
armLen[i] = curArmLen
// 新的串超出之前子串的范围，用新的范围覆盖
if i+curArmLen > right {
mid = i
right = i + curArmLen
}
// 当前结果大于之前的结果
if (curArmLen<<1)+1 > end-start {
start = i - curArmLen
end = i + curArmLen
}
// 如果后面的剩下的字符不够最大臂长就没必要进行下去了
if i+((end-start)>>1) >= len(ns) {
break
}
}
return string(s[start>>1 : end>>1])
}
c++
class Solution {
private:
int expand(string s, int left, int right) {
while (left >= 0 && right < s.length() && s[left] == s[right]) {
--left;
++right;
}
return (right - left - 2) >> 1;
}
public:
string longestPalindrome(string s) {
// 在字符之间加入#号，使得字符数恒定变为奇数
string ns = "#";
for (char c: s) {
ns += c;
ns += "#";
}
// 最终结果的头尾下标
int start = 0, end = 0;
// 臂长缓存
int armLen[ns.length()];
memset(armLen, 0, sizeof(int) * ns.length());
// 之前回文串的右边界,之前回文串的中位下标
int right = 0, mid = 0;
for (int i = 0; i < ns.length(); ++i) {
// 判断是否有过臂长缓存
int minArmLen;
if (right > i) {
minArmLen = min(armLen[(mid << 1) - i], right - i);
} else {
minArmLen = 0;
}
// 当前臂长
int curArmLen = expand(ns, i - minArmLen, i + minArmLen);
// 将当前臂长缓存
armLen[i] = curArmLen;
// 新的串超出之前子串的范围，用新的范围覆盖
if (i + curArmLen > right) {
mid = i;
right = i + curArmLen;
}
// 当前结果大于之前的结果
if ((curArmLen << 1) + 1 > end - start) {
start = i - curArmLen;
end = i + curArmLen;
}
// 如果后面的剩下的字符不够最大臂长就没必要进行下去了
if (i + ((end - start) >> 1) >= ns.length()) {
break;
}
}
return s.substr(start >> 1, (end - start) >> 1);
}
};
c
int expand(char *s, int l, int left, int right) {
while (left >= 0 && right < l && s[left] == s[right]) {
--left;
++right;
}
return (right - left - 2) >> 1;
}
char *longestPalindrome(char *s) {
const int l = strlen(s);
const int nsl = (l << 1) + 1;
char ns[nsl];
ns[0] = '#';
for (int i = 0; i < l; ++i) {
ns[(i << 1) + 1] = s[i];
ns[(i + 1) << 1] = '#';
}
// 最终结果的头尾下标
int start = 0, end = 0;
// 臂长缓存
int armLen[nsl];
memset(armLen, 0, sizeof(int) * nsl);
// 之前回文串的右边界,之前回文串的中位下标
int right = 0, mid = 0;
for (int i = 0; i < nsl; ++i) {
// 判断是否有过臂长缓存
int minArmLen;
if (right > i) {
minArmLen = fmin(armLen[(mid << 1) - i], right - i);
} else {
minArmLen = 0;
}
// 当前臂长
int curArmLen = expand(ns, nsl, i - minArmLen, i + minArmLen);
// 将当前臂长缓存
armLen[i] = curArmLen;
// 新的串超出之前子串的范围，用新的范围覆盖
if (i + curArmLen > right) {
mid = i;
right = i + curArmLen;
}
// 当前结果大于之前的结果
if ((curArmLen << 1) + 1 > end - start) {
start = i - curArmLen;
end = i + curArmLen;
}
// 如果后面的剩下的字符不够最大臂长就没必要进行下去了
if (i + ((end - start) >> 1) >= nsl) {
break;
}
}
s[end >> 1] = 0;
return s + (start >> 1);
}
python
class Solution:
def longestPalindrome(self, s: str) -> str:
def expand(s: str, left: int, right: int) -> int:
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return (right - left - 2) >> 1
# 在字符之间加入 # 号，使得字符数恒定变为奇数
ns = "#"
for i in range(len(s)):
ns += s[i]
ns += '#'
# 最终结果的头尾下标
start, end = 0, 0
# 臂长缓存
armLen = [0] * len(ns)
# 之前回文串的右边界, 之前回文串的中位下标
right, mid = 0, 0
for i in range(len(ns)):
# 判断是否有过臂长缓存
minArmLen = 0
if right > i:
minArmLen = min(armLen[(mid << 1) - i], right - i)
# 当前臂长
curArmLen = expand(ns, i - minArmLen, i + minArmLen)
# 将当前臂长缓存
armLen[i] = curArmLen
# 新的串超出之前子串的范围，用新的范围覆盖
if i + curArmLen > right:
mid = i
right = i + curArmLen
# 当前结果大于之前的结果
if (curArmLen << 1) + 1 > end - start:
start = i - curArmLen
end = i + curArmLen
# 如果后面的剩下的字符不够最大臂长就没必要进行下去了
if i + ((end - start) >> 1) >= len(ns):
break
return s[start >> 1: end >> 1]
java
class Solution {
public String longestPalindrome(String s) {
// 在字符之间加入#号，使得字符数恒定变为奇数
char[] ns = new char[(s.length() << 1) + 1];
ns[0] = '#';
for (int i = 0; i < s.length(); ++i) {
ns[(i << 1) + 1] = s.charAt(i);
ns[(i + 1) << 1] = '#';
}
// 最终结果的头尾下标
int start = 0, end = 0;
// 臂长缓存
int[] armLen = new int[ns.length];
// 之前回文串的右边界,之前回文串的中位下标
int right = 0, mid = 0;
for (int i = 0; i < ns.length; ++i) {
// 判断是否有过臂长缓存
int minArmLen;
if (right > i) {
minArmLen = Math.min(armLen[(mid << 1) - i], right - i);
} else {
minArmLen = 0;
}
// 当前臂长
int curArmLen = expand(ns, i - minArmLen, i + minArmLen);
// 将当前臂长缓存
armLen[i] = curArmLen;
// 新的串超出之前子串的范围，用新的范围覆盖
if (i + curArmLen > right) {
mid = i;
right = i + curArmLen;
}
// 当前结果大于之前的结果
if ((curArmLen << 1) + 1 > end - start) {
start = i - curArmLen;
end = i + curArmLen;
}
// 如果后面的剩下的字符不够最大臂长就没必要进行下去了
if (i + ((end - start) >> 1) >= ns.length) {
break;
}
}
return s.substring(start >> 1, end >> 1);
}
private int expand(char[] s, int left, int right) {
while (left >= 0 && right < s.length && s[left] == s[right]) {
--left;
++right;
}
return (right - left - 2) >> 1;
}
}
非常感谢你阅读本文~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://bbs.huaweicloud.com/community/usersnew/id_1628396583336561 博客原创~
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）