LCD1602显示不全。

Question

 

Answer 1

让阿豪来帮你解答，本回答参考chatgpt3.5编写提供，如果还有疑问可以评论或留言

问题描述： 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例 1： 输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。 示例 2： 输入: "cbbd" 输出: "bb" 代码实现： 方法一：暴力枚举

1. 首先我们得到字符串 s 的长度 n
2. 然后我们遍历整个 s 字符串，枚举出所有的子串，共有 n(n+1)/2 个子串
3. 对于所有的子串，判断它是否是回文字符串

4. 如果该子串是回文字符串，判断它是否是最长的回文子串，并记录该子串的起点位置和子串长度 代码如下： class Solution { public: string longestPalindrome(string s) { int n = s.length(); if (n == 0) return ""; int start = 0, maxlen = 1; for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { int len = j - i + 1; if (len > maxlen && isPalindrome(s, i, j)) { start = i; maxlen = len; } } } return s.substr(start, maxlen); }

   bool isPalindrome(string s, int left, int right) { while (left < right) { if (s[left] != s[right]) { return false; } left++; right--; } return true; } }; 时间复杂度：O(n^3)，暴力枚举所有的子串，每个子串需要判断是否是回文字符串，所以需要 O(n) 的时间复杂度，总时间复杂度为 O(n^3)。 方法二：动态规划

5. 首先定义一个二维数组 dp，其中 dp[i][j] 表示 s 中从 i 到 j 的字串是否是回文子串
6. 当 i = j 时，dp[i][j] = true，表示长度为 1 的字符串一定是回文字符串
7. 当 i < j 时，如果 s[i] == s[j] 且 s[i+1][j-1] 是回文字符串，则 dp[i][j] 也是回文字符串
8. 记录下最长的回文子串，并返回它 代码如下： class Solution { public: string longestPalindrome(string s) { int n = s.length(); if (n == 0) return ""; bool dp[n][n] = {false}; int maxlen = 1, start = 0; for (int i = n-1; i >= 0; i--) { for (int j = i; j < n; j++) { if (s[i] == s[j] && (j-i < 3 || dp[i+1][j-1])) { dp[i][j] = true; if (j-i+1 > maxlen) { start = i; maxlen = j-i+1; } } } } return s.substr(start, maxlen); } }; 时间复杂度：O(n^2)，需要判断 n(n+1)/2 个子串是否是回文字符串，每个子串需要 O(n) 的时间复杂度，所以总时间复杂度为 O(n^2)。 方法三：中心扩展法
9. 首先遍历整个字符串，以每个字符为中心分别向两边扩展，得到奇数长度的回文字符串
10. 然后再以每个字符和它右侧的字符为中心分别向两边扩展，得到偶数长度的回文字符串

11. 返回最长的回文字符串 代码如下： class Solution { public: string longestPalindrome(string s) { int n = s.length(); if (n == 0) return ""; int maxlen = 1, start = 0; for (int i = 0; i < n; i++) { int len1 = expandAroundCenter(s, i, i); // 奇数长度的回文字符串 int len2 = expandAroundCenter(s, i, i+1); // 偶数长度的回文字符串 int len = max(len1, len2); if (len > maxlen) { maxlen = len; start = i - (maxlen-1)/2; } } return s.substr(start, maxlen); }

    int expandAroundCenter(string s, int left, int right) { while (left >= 0 && right < s.length() && s[left] == s[right]) { left--; right++; } return right-left-1; // 注意减一 } }; 时间复杂度：O(n^2)，需要遍历整个字符串，以每个字符为中心扩展，同时以每个字符和它右侧的字符为中心扩展，每次扩展需要 O(n) 的时间复杂度，所以总时间复杂度为 O(n^2)。