【力扣】05最长的回文子串

标题链接：https://leetcode.cn/problems/longest-palindromic-substring/description/?envType=study-plan-v2&envId=top-100-liked
难度：中等
标题描述

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例

• 输入: “babad”
  输出: “bab”
  注意: “aba” 也是一个有效答案。
  
• 输入: “cbbd”
  输出: “bb”
  

我的答案：

1. class Solution {
2.     public String longestPalindrome(String s) {
3.           //字符数组
4.         char[] chars = s.toCharArray();
5.         int maxlength = 0;//计数器
6.         int index = 0;//起始下标
7.         for (int i = 0; i < chars.length; i++) {//起始下标i
8.             //结束下标j
9.             for (int j = i; j < chars.length; j++) {
10.                 boolean flag = true;//假设是回文串
11.                 //计算当前的串长度abbcbba  7
12.                 int longs = j - i + 1;
13.                 for (int k = 0; k < longs; k++) {//遍历当前串是不是回文串
14.                     if (chars[i + k] != chars[j - k]) {
15.                         //如果有字符不相等,说明不是回文串
16.                         flag = false;
17.                         break;
18.                     }
19.                 }
20.                 //如果长度大于之前计数器的值并且是回文串则赋值
21.                 if (longs > maxlength && flag) {
22.                     //回文串长度
23.                     maxlength = longs;
24.                     //起始下标
25.                     index = i;
26.                 }
27.             }
28.         }
29.         //由找到的最长的回文串的起始下标index和长度length,截取
30.         //原字符串返回截取的字符串
31.         return s.substring(index, index + maxlength);
32.     }
33. }

复制代码

1. package test;
2. /**
3. * @Author Stringzhua
4. * @Date 2024/11/8 19:07
5. * description:
6. */
7. public class test02 {
8.     public static void main(String[] args) {
9. //        String s = "abbcbba";
10.         String s = "abbcbbaaaa";
11.         System.out.println(check(s));
12.     }
14.     public static String check(String s) {
15.         //字符数组
16.         char[] chars = s.toCharArray();
17.         int maxlength = 0;//计数器
18.         int index = 0;//起始下标
19.         for (int i = 0; i < chars.length; i++) {//起始下标i
20.             //结束下标j
21.             for (int j = i; j < chars.length; j++) {
22.                 boolean flag = true;//假设是回文串
23.                 //计算当前的串长度abbcbba  7
24.                 int longs = j - i + 1;
25.                 for (int k = 0; k < longs; k++) {//遍历当前串是不是回文串
26.                     if (chars[i + k] != chars[j - k]) {
27.                         //如果有字符不相等,说明不是回文串
28.                         flag = false;
29.                         break;
30.                     }
31.                 }
32.                 //如果长度大于之前计数器的值并且是回文串则赋值
33.                 if (longs > maxlength && flag) {
34.                     //回文串长度
35.                     maxlength = longs;
36.                     //起始下标
37.                     index = i;
38.                 }
39.             }
40.         }
41.         //由找到的最长的回文串的起始下标index和长度length,截取
42.         //原字符串返回截取的字符串
43.         return s.substring(index, index + maxlength);
44.     }
45. }

复制代码

解题思路

• 暴力解法（Brute Force）
  
  
  
  • 遍历字符串的全部子串，判断每个子串是否为回文串。
    
  • 从最长的子串开始遍历，一旦找到回文子串，就返回该子串。
    
  • 时间复杂度：                                                  O                                  (                                               n                                     3                                              )                                          O(n^3)                           O(n3)，此中                                                   n                                          n                           n 是字符串的长度。对于每个子串，判断其是否为回文串需要                                                   O                                  (                                  n                                  )                                          O(n)                           O(n) 的时间，总共有                                                   O                                  (                                               n                                     2                                              )                                          O(n^2)                           O(n2) 个子串，所以时间复杂度为                                                   O                                  (                                               n                                     3                                              )                                          O(n^3)                           O(n3)。
    
  • 空间复杂度：                                                  O                                  (                                  1                                  )                                          O(1)                           O(1)，只需要常数级别的额外空间。
    
  
  

1. public class LongestPalindromeSubstring {
2.    public static String longestPalindrome(String s) {
3.         int n = s.length();
4.         if (n == 0) return "";
5.         String longest = "";
6.         for (int i = 0; i < n; i++) {
7.             for (int j = i; j < n; j++) {
8.                 // 剪枝操作，如果当前子串长度小于等于已找到的最长回文子串长度，直接跳过
9.                 if (j - i + 1 <= longest.length()) continue;
10.                 String substring = s.substring(i, j + 1);
11.                 if (isPalindrome(substring)) {
12.                     longest = substring;
13.                 }
14.             }
15.         }
16.         return longest;
17.     }
19.     private static boolean isPalindrome(String s) {
20.         int i = 0, j = s.length() - 1;
21.         while (i < j) {
22.             if (s.charAt(i++)!= s.charAt(j--)) return false;
23.         }
24.         return true;
25.     }
26. }

复制代码

• 动态规划（Dynamic Programming）
  
  
  
  • 定义状态：设 dp[j] 表示字符串 s 从索引 i 到索引 j 的子串是否为回文串。
    
  • 状态转移方程：
    
    
    
    • 当 i == j 时，dp[j] = true，单个字符是回文串。
      
    • 当 j - i == 1 时，dp[j] = (s == s[j])，两个相邻相同字符是回文串。
      
    • 当 j - i > 1 时，dp[j] = (s == s[j]) && dp[i + 1][j - 1]，即首尾字符相同且中心子串也是回文串。
      
    
    
  • 遍历次序：从长度为1的子串开始，逐步计算长度更长的子串是否为回文串，先计算 dp，再计算 dp[i + 1]，然后计算长度为3及以上的子串。
    
  • 时间复杂度：                                                  O                                  (                                               n                                     2                                              )                                          O(n^2)                           O(n2)，计算 dp 数组需要两层循环，每层循环最多实行                                                   n                                          n                           n 次。
    
  • 空间复杂度：                                                  O                                  (                                               n                                     2                                              )                                          O(n^2)                           O(n2)，需要一个二维数组来生存状态。
    
  
  

1. public class LongestPalindromeSubstring {
2.    public static String longestPalindrome(String s) {
3.        int n = s.length();
4.        if (n == 0) return "";
5.        boolean[][] dp = new boolean[n][n];
6.        String longest = "";
7.        for (int len = 1; len <= n; len++) {
8.            for (int i = 0; i <= n - len; i++) {
9.                int j = i + len - 1;
10.                if (len == 1) {
11.                    dp[i][j] = true;
12.                } else if (len == 2) {
13.                    dp[i][j] = s.charAt(i) == s.charAt(j);
14.                } else {
15.                    dp[i][j] = s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1];
16.                }
17.                if (dp[i][j] && len > longest.length()) {
18.                    longest = s.substring(i, j + 1);
19.                }
20.            }
21.        }
22.        return longest;
23.    }
24. }

复制代码

• 中央扩展法（Expand Around Center）
  
  
  
  • 遍历字符串的每个字符，以该字符为中央向双方扩展，判断是否为回文串。
    
  • 思量两种情况：奇数长度回文串（以单个字符为中央）和偶数长度回文串（以相邻两个相同字符为中央）。
    
  • 时间复杂度：                                                  O                                  (                                               n                                     2                                              )                                          O(n^2)                           O(n2)，对于每个字符，最多需要向双方扩展                                                   O                                  (                                  n                                  )                                          O(n)                           O(n) 次。
    
  • 空间复杂度：                                                  O                                  (                                  1                                  )                                          O(1)                           O(1)，只需要常数级别的额外空间。
    代码实现：
    
  
  

1. public class LongestPalindromeSubstring {
2.    public static String longestPalindrome(String s) {
3.        if (s == null || s.length() == 0) return "";
4.        int start = 0, end = 0;
5.        for (int i = 0; i < s.length(); i++) {
6.            int len1 = expandAroundCenter(s, i, i);
7.            int len2 = expandAroundCenter(s, i, i + 1);
8.            int len = Math.max(len1, len2);
9.            if (len > end - start) {
10.                start = i - (len - 1) / 2;
11.                end = i + len / 2;
12.            }
13.        }
14.        return s.substring(start, end + 1);
15.    }
17.    private static int expandAroundCenter(String s, int left, int right) {
18.        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
19.            left--;
20.            right++;
21.        }
22.        return right - left - 1;
23.    }
24. }

复制代码

• Manacher算法（优化的中央扩展法）
  
  
  
  • 预处理字符串，在每个字符前后插入特殊字符（如 #），将奇数和偶数长度的回文串统一处理。
    
  • 使用一个辅助数组 p 来记载以每个字符为中央的最长回文半径。
    
  • 使用已经计算的回文半径信息，减少不须要的比较。
    
  • 时间复杂度：                                                  O                                  (                                  n                                  )                                          O(n)                           O(n)，虽然有两层循环，但内层循环的总实行次数不超过                                                   O                                  (                                  n                                  )                                          O(n)                           O(n)。
    
  • 空间复杂度：                                                  O                                  (                                  n                                  )                                          O(n)                           O(n)，需要一个辅助数组 p 来生存最长回文半径。
    
  
  

1. public class LongestPalindromeSubstring {
2.     public static String longestPalindrome(String s) {
3.         // 预处理字符串
4.         String T = preprocess(s);
5.         int n = T.length();
6.         int[] P = new int[n];
7.         int C = 0, R = 0;
8.         for (int i = 1; i < n - 1; i++) {
9.             int i_mirror = 2 * C - i;
10.             if (R > i) {
11.                 P[i] = Math.min(R - i, P[i_mirror]);
12.             } else {
13.                 P[i] = 0;
14.             }
15.             // 尝试扩展以i为中心的回文子串
16.             while (T.charAt(i + 1 + P[i]) == T.charAt(i - 1 - P[i])) {
17.                 P[i]++;
18.             }
19.             // 如果以i为中心的回文子串扩展后超过了R，更新C和R
20.             if (i + P[i] > R) {
21.                 C = i;
22.                 R = i + P[i];
23.             }
24.         }
25.         // 找到P中的最大值
26.         int maxLen = 0;
27.         int centerIndex = 0;
28.         for (int i = 1; i < n - 1; i++) {
29.             if (P[i] > maxLen) {
30.                 maxLen = P[i];
31.                 centerIndex = i;
32.             }
33.         }
34.         int start = (centerIndex - maxLen) / 2;
35.         return s.substring(start, start + maxLen);
36.     }
38.     private static String preprocess(String s) {
39.         StringBuilder sb = new StringBuilder();
40.         sb.append("$#");
41.         for (int i = 0; i < s.length(); i++) {
42.             sb.append(s.charAt(i));
43.             sb.append('#');
44.         }
45.         sb.append('@');
46.         return sb.toString();
47.     }
48. }

复制代码

Manacher 算法的主要头脑是通过预处理字符串，使得可以用统一的方式处理奇数长度和偶数长度的回文串。然后使用已经计算的回文半径信息，减少不须要的比较，从而将时间复杂度降低到线性。在上述代码中，preprocess方法用于预处理字符串，在每个字符前后插入特殊字符。然后通过for循环计算每个字符为中央的最长回文半径，并记载最长回文子串的相关信息，最后返回最长回文子串。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。