☆打卡算法☆LeetCode 214. 最短回文串 算法解析
☆打卡算法☆LeetCode 214. 最短回文串 算法解析
恬静的小魔龙
发布于 2022-09-27 09:39:41
发布于 2022-09-27 09:39:41
大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。
一、题目
1、算法题目
“给定一个字符串，通过在字符串前面添加字符转换为回文串，找到并返回转换的最短回文串。”
题目链接：
来源：力扣（LeetCode）
2、题目描述
给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。
示例 1：
输入： s = "aacecaaa"
输出： "aaacecaaa"示例 2：
输入： s = "abcd"
输出： "dcbabcd"二、解题
1、思路分析
这道题要求给定一字符串，将字符串添加字符转为为回文串，返回这种方法转换的最短回文串。
这道题可以等价于找到字符串的最长回文前缀，比如 s = "aacecaaa" 的最长回文前缀为 "aacecaa"， 那么将其作为最终回文串的中心，再反转后面的非回文串放到前面即可。
回文是指正反方向读起来都一样的字符串，字符串s[0]是字符串的s的最短回文前缀。
可以发现不论是怎样的字符串，都至少存在一个字符可以作为回文串的中心，比如 "abcd" 中 a可以作为中心。
最长的回文前缀这个回文串的中心一定小于 (n+1)/2，而且回文串的左边界需要刚好达到字符串的开头，可以使用中心扩展法，枚举将0 ~ (n+1)/2内的值 作为中心的 所有回文串，找到最长的回文前缀。
2、代码实现
代码参考：
class Solution {
public String shortestPalindrome(String s) {
char[] arr = s.toCharArray();
int n = arr.length;
if(n == 0) {
return "";
}
int max = -1;
for(int i = 0; i < (n + 1) / 2; ++i) {
int len1 = expand(arr, i, i);
int len2 = expand(arr, i, i + 1);
int len = Math.max(len1, len2);
// 回文串的长度刚好可以到达左边界 0
if(i - (len - 1) / 2 == 0) {
max = Math.max(max, len);
}
}
String last = s.substring(max);
return new StringBuilder(last).reverse() + s.substring(0, max) + last;
}
// 中心扩展
public int expand(char[] arr, int l, int r) {
while(l >= 0 && r < arr.length && arr[l] == arr[r]) {
l--; r++;
}
return r - l - 1;
}
}
image.png
3、时间复杂度
时间复杂度：O(|s|)
其中s是字符串的长度。
空间复杂度：O(1)
只需要常数级的变量空间。
三、总结
总结一下：
无论是怎样的字符串，都存在一个字符可以作为回文串的中心。
先找到这个中心，然后回文串的左边界需要达到字符串的开头。
使用中心拓展法枚举这种中心的(n+1)/2的边界内的所有值，判断可以作为中心的所有回文串。
找到最长的回文前缀。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2022-08-26，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录