最长回文子串

字数 1070 2025-10-25 23:10:25

最长回文子串

题目描述：给定一个字符串s，找到s中最长的回文子串。回文串是指正着读和反着读都一样的字符串。例如，对于输入"babad"，最长回文子串可能是"bab"或"aba"；对于输入"cbbd"，最长回文子串是"bb"。

解题过程：

问题分析：
我们需要找到一个字符串中的最长连续子串，这个子串是回文的。一个直接的思路是检查所有可能的子串，判断其是否为回文，但这样时间复杂度会很高（O(n^3)）。我们可以使用动态规划来优化。
定义状态：
我们定义一个二维布尔数组dp，其中dp[i][j]表示字符串s中从索引i到索引j的子串（即s[i..j]）是否为回文串。
状态转移方程：
一个子串s[i..j]是回文串，需要满足两个条件：
- 子串两端的字符相等：s[i] == s[j]
- 去掉两端字符后的子串是回文串（或者子串长度很小）：即s[i+1..j-1]是回文串，或者子串长度小于等于3（此时只要两端字符相等就一定是回文）
  因此，状态转移方程为：
  dp[i][j] = (s[i] == s[j]) and (j - i < 3 or dp[i+1][j-1])
初始化：
单个字符一定是回文串，所以所有dp[i][i] = true。
对于长度为2的子串，如果两个字符相同，那么也是回文串。
计算顺序：
由于dp[i][j]依赖于dp[i+1][j-1]（即左下方的值），我们需要从子串长度较小的情况开始计算。因此，我们按子串长度L从1到n（字符串长度）进行遍历，对于每个长度，遍历所有可能的起始位置i。
记录结果：
在计算过程中，我们记录找到的最长回文子串的起始位置和长度（或者直接记录子串本身）。
算法步骤：
- 初始化dp表格，所有元素为false
- 设置start=0, maxLen=1（单个字符是最小的回文串）
- 对于长度L从1到n：
  - 对于起始位置i从0到n-L：
    - 计算结束位置j = i + L - 1
    - 如果s[i] == s[j]且(L <= 2或dp[i+1][j-1]为true)：
      - 设置dp[i][j] = true
      - 如果L > maxLen：
        
        更新start = i, maxLen = L
- 返回s.substring(start, start + maxLen)
复杂度分析：
- 时间复杂度：O(n²)，需要填充n²的dp表格
- 空间复杂度：O(n²)，用于存储dp表格

通过这个动态规划方法，我们可以在多项式时间内找到最长回文子串，比暴力解法高效很多。

最长回文子串题目描述：给定一个字符串s，找到s中最长的回文子串。回文串是指正着读和反着读都一样的字符串。例如，对于输入"babad"，最长回文子串可能是"bab"或"aba"；对于输入"cbbd"，最长回文子串是"bb"。解题过程：问题分析：我们需要找到一个字符串中的最长连续子串，这个子串是回文的。一个直接的思路是检查所有可能的子串，判断其是否为回文，但这样时间复杂度会很高（O(n^3)）。我们可以使用动态规划来优化。定义状态：我们定义一个二维布尔数组dp，其中dp[ i][ j]表示字符串s中从索引i到索引j的子串（即s[ i..j ]）是否为回文串。状态转移方程：一个子串s[ i..j ]是回文串，需要满足两个条件：子串两端的字符相等：s[ i] == s[ j ] 去掉两端字符后的子串是回文串（或者子串长度很小）：即s[ i+1..j-1 ]是回文串，或者子串长度小于等于3（此时只要两端字符相等就一定是回文）因此，状态转移方程为： dp[ i][ j] = (s[ i] == s[ j]) and (j - i < 3 or dp[ i+1][ j-1 ]) 初始化：单个字符一定是回文串，所以所有dp[ i][ i ] = true。对于长度为2的子串，如果两个字符相同，那么也是回文串。计算顺序：由于dp[ i][ j]依赖于dp[ i+1][ j-1 ]（即左下方的值），我们需要从子串长度较小的情况开始计算。因此，我们按子串长度L从1到n（字符串长度）进行遍历，对于每个长度，遍历所有可能的起始位置i。记录结果：在计算过程中，我们记录找到的最长回文子串的起始位置和长度（或者直接记录子串本身）。算法步骤：初始化dp表格，所有元素为false 设置start=0, maxLen=1（单个字符是最小的回文串）对于长度L从1到n：对于起始位置i从0到n-L：计算结束位置j = i + L - 1 如果s[ i] == s[ j]且(L <= 2或dp[ i+1][ j-1 ]为true)：设置dp[ i][ j ] = true 如果L > maxLen：更新start = i, maxLen = L 返回s.substring(start, start + maxLen) 复杂度分析：时间复杂度：O(n²)，需要填充n²的dp表格空间复杂度：O(n²)，用于存储dp表格通过这个动态规划方法，我们可以在多项式时间内找到最长回文子串，比暴力解法高效很多。