有的时候博客内容会有变动，首发博客是最新的，其他博客地址可能会未同步,认准
https://blog.zysicyj.top
全网最细面试题手册，支持艾宾浩斯记忆法。这是一份最全面、最详细、最高质量的 java面试题，不建议你死记硬背，只要每天复习一遍，有个大概印象就行了。 https://store.amazingmemo.com/chapterDetail/1685324709017001`
最长回文子串问题
在字符串处理中，最长回文子串问题是一个经典问题，它要求找到一个给定字符串中最长的子串，这个子串无论从前向后读还是从后向前读都是相同的。
解决方法
有几种不同的方法可以解决这个问题，包括动态规划、中心扩展算法和Manacher算法。
动态规划
动态规划的方法是创建一个二维数组dp[i][j]，其中i和j分别表示字符串中的开始和结束索引，dp[i][j]表示从i到j的子串是否是回文串。
public String longestPalindromeDP(String s) {
if (s == null || s.length() < 1) {
return "";
}
int n = s.length();
boolean[][] dp = new boolean[n][n];
String res = "";
for (int len = 0; len < n; len++) {
for (int start = 0; start + len < n; start++) {
int end = start + len;
dp[start][end] = (len == 0 || len == 1 || dp[start + 1][end - 1]) && s.charAt(start) == s.charAt(end);
if (dp[start][end] && len + 1 > res.length()) {
res = s.substring(start, end + 1);
}
}
}
return res;
}
中心扩展算法
中心扩展算法的思想是，对于每个可能的回文中心（字符或两个字符之间的空隙），向两边扩展，直到不能形成更长的回文串。
public String longestPalindromeExpandAroundCenter(String s) {
if (s == null || s.length() < 1) {
return "";
}
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
int len1 = expandAroundCenter(s, i, i);
int len2 = expandAroundCenter(s, i, i + 1);
int len = Math.max(len1, len2);
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substring(start, end + 1);
}
private int expandAroundCenter(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
return right - left - 1;
}
Manacher算法
Manacher算法是解决最长回文子串问题的最优算法，时间复杂度为O(n)。它通过在字符之间插入分隔符（通常是一个不会在输入字符串中出现的字符，如#），将奇数长度和偶数长度的回文统一处理。
public String longestPalindromeManacher(String s) {
// 此处省略Manacher算法的实现细节
// 通常包括预处理字符串，在每个字符之间插入分隔符
// 然后使用Manacher算法的核心逻辑来找到最长回文子串
// 最后从处理后的字符串中提取出原始字符串的最长回文子串
return "";
}
总结
以上就是解决最长回文子串问题的三种常见方法。动态规划的时间复杂度为O(n^2)，空间复杂度也为O(n^2)；中心扩展算法的时间复杂度为O(n^2)，但空间复杂度降低到了O(1)；Manacher算法提供了最优的时间复杂度O(n)，但实现起来相对复杂。在实际应用中，可以根据具体情况选择合适的算法。
本文是原创文章，采用 CC BY-NC-SA 4.0 协议，完整转载请注明来自 小朱
评论
隐私政策
0/500
滚动到此处加载评论...