给你一个字符串 s，找到 s 中最长的回文子串。 如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。 示例 1： 输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。 示例 2： 输入：s = "cbbd" 输出："bb" 提示： 1 <= s.length <= 1000 s 仅由数字和英文字母组成

### 回答1： 最长回文子串可以使用动态规划算法来解决。首先，定义一个二维数组dp[i][j]表示字符串s[i...j]是否为回文字符串，若是则为1，否则为0。初始化时，dp[i][i]=1，即单个字符为回文字符串；同时，对于任意相邻的两个字符s[i]与s[i+1]，若它们相等，则dp[i][i+1]=1，即两个字符相等也是回文字符串。接下来，从长度3到len遍历所有子串，对于每个子串s[i...j]，若s[i]==s[j]并且s[i+1...j-1]也是回文字符串，则有dp[i][j]=1，否则为0。最终，遍历二维数组dp，找到最长的回文子串即可。 代码如下： ``` class Solution { public: string longestPalindrome(string s) { int len = s.length(); vector<vector<int>> dp(len, vector<int>(len, 0)); string res = ""; for(int i=len-1; i>=0; i--) { for(int j=i; j<len; j++) { dp[i][j] = (s[i]==s[j] && (j-i<=2 || dp[i+1][j-1])); if(dp[i][j] && j-i+1>res.length()) { res = s.substr(i, j-i+1); } } } return res; } }; ``` ### 回答2： 给定一个字符串s，我们需要找出其中最长的回文子串。 解决这个问题的一种常见方法是使用动态规划。我们可以定义一个二维数组dp，其中dp[i][j]表示以s[i]到s[j]所组成的子串是否为回文子串。当i=j时，表示长度为1的子串，必定是回文子串；当i=j+1时，表示长度为2的子串，只有s[i]和s[j]相同时才是回文子串。对于长度大于2的子串，如果s[i]和s[j]相等且dp[i+1][j-1]为真，则dp[i][j]为真。 通过动态规划，我们可以填充dp数组，找出最长的回文子串的位置。具体步骤如下： 1. 初始化dp数组，将长度为1的子串设为True。 2. 遍历字符串s，计算长度为2的子串是否为回文子串，并更新dp数组。 3. 对于长度大于2的子串，根据上述规则计算并更新dp数组。 4. 统计dp数组中最长的回文子串的位置和长度。 5. 根据最长子串的位置和长度，获取该子串。 这种方法的时间复杂度为O(n^2)，空间复杂度为O(n^2)。其中，n是字符串s的长度。 另外，还可以通过中心扩展的方式解决该问题。具体步骤如下： 1. 遍历字符串s，以每个字符为中心，向两侧扩展，找出以该字符为中心的最长回文子串。 2. 遍历字符串s，以每两个相邻字符中间为中心，向两侧扩展，找出以该中间位置为中心的最长回文子串。 3. 统计并更新最长回文子串的位置和长度。 4. 根据最长子串的位置和长度，获取该子串。 这种方法的时间复杂度为O(n^2)，空间复杂度为O(1)。其中，n是字符串s的长度。 综上所述，我们可以通过动态规划或中心扩展的方式找到字符串s中最长的回文子串。 ### 回答3： 要找到字符串 s 中最长的回文子串，可以使用动态规划的方法。首先，定义一个二维数组 dp，其中 dp[i][j] 表示字符串 s 从索引 i 到 j 的子串是否是回文串。 为了计算 dp[i][j]，需要对三种情况进行判断： 1. 当 i == j 时，即子串长度为 1，该子串一定是回文字符串。 2. 当 j = i + 1 时，即子串长度为 2，需要判断 s[i] 是否等于 s[j]。 3. 当 j > i + 1 时，即子串长度大于 2，需要判断 s[i] 是否等于 s[j]，并且判断 dp[i+1][j-1] 是否为回文串。 根据以上三种情况的判断，可以写出动态规划的算法： 1. 初始化 dp 数组，将所有 dp[i][i] 的元素设为 true。 2. 使用变量 maxLength 记录最长的回文子串长度，使用变量 start 记录最长回文子串的起始位置。 3. 从长度 2 开始遍历所有子串长度，从字符串的起始位置往后遍历，因为长度为 1 的子串已经计算过了。 4. 在遍历过程中，根据上述判断条件更新 dp 数组的值。 5. 如果找到一个更长的回文子串，则更新 maxLength 和 start。 6. 最后，根据 maxLength 和 start 可以得到最长的回文子串。 具体的算法实现如下： ```python def longestPalindrome(s: str) -> str: n = len(s) dp = [[False] * n for _ in range(n)] maxLength = 1 start = 0 for i in range(n): dp[i][i] = True for length in range(2, n + 1): for i in range(n - length + 1): j = i + length - 1 if s[i] == s[j]: if length == 2 or dp[i + 1][j - 1]: dp[i][j] = True if length > maxLength: maxLength = length start = i return s[start: start + maxLength] ``` 以上算法的时间复杂度为 O(n^2)，其中 n 是字符串 s 的长度。

C 语言中求最长回文子串的常见方法有以下几种： 1. 暴力枚举法：枚举每个子串，并判断该子串是否是回文串，是则更新最长回文子串的长度。时间复杂度为 O(n^3)。 2. Manacher 算法：时间复杂度为 O(n)。 3. DP：以每个字符为回文子串中心，向两边扩展，判断回文性，并更新最长回文子串的长度。时间复杂度为 O(n^2)。 这三种方法的实现细节和代码可以在网上找到更详细的资料。