leetcode-5.最长回文子串

题目 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例一 输入: “babad” 输出: “bab” 注意: “aba” 也是一个有效答案。 示例二 输入: “cbbd” 输出: “bb” 代码 先说一下最容易想到的，动态规划解决 public static String longestPalindrome(String s) { //如果s的长度为1或0直接返回 if(s.length()==0||s.length()==1){return s;} //创建一个boolean数组，用于存储j到i的位置的 在编程领域，LeetCode 是一个著名的在线平台，它提供了各种算法和编程问题供开发者练习和提升技能。"LeetCode-5. 最长回文子串"是其中一道经典的字符串处理问题，目标是从给定的字符串中找出最长的回文子串。回文串是指正读反读都能读通的字符串，例如 "abcba" 和 "abccba"。 这道题目给出了一些示例，例如输入字符串 "babad"，输出可以是 "bab" 或 "aba"，因为它们都是给定字符串中的回文子串。另一个示例是输入 "cbbd"，输出为 "bb"，这是该字符串中最长的回文子串。 解决这个问题有多种方法，其中包括动态规划和中心扩展法。以下是两种常见的解决方案： 1. **动态规划**： 动态规划是一种通过构建状态转移表来解决问题的方法。在这个问题中，我们可以创建一个二维布尔数组 `nums`，其中 `nums[i][j]` 表示字符串 `s` 从索引 `i` 到 `j` 的子串是否是回文。状态转移方程可以表示为 `nums[i][j] = (s.charAt(i) == s.charAt(j)) && (i + 1 < j ? nums[i + 1][j - 1] : true)`。初始时，所有长度为1的子串都是回文，然后逐步扩展。找到最长的回文子串的起始位置和长度，并返回子串。 2. **中心扩展法**： 中心扩展法的思想是从每个可能的子串中心开始向外扩展，检查扩展后的子串是否为回文。这个方法可以分为单字符中心和双字符中心两种情况。对于每个字符，向两边扩展并记录最长的回文子串。同时，为了确保找到全局最优解，我们需要维护一个变量来记录最长回文子串的长度和起始位置。 在提供的代码中，第一段是使用动态规划的方法，创建了一个二维数组 `nums` 来存储子串是否为回文的信息，然后通过两层循环遍历所有可能的子串，当找到一个更长的回文子串时更新记录。第二段代码是采用中心扩展法，用两个指针 `left` 和 `right` 分别代表回文子串的中心，不断尝试扩展并更新最长回文子串的长度和起始位置。 解决这类问题的关键在于理解回文串的特性，并选择合适的数据结构和算法来有效地搜索和验证回文子串。通过这样的练习，可以提高对字符串操作、动态规划和双指针等编程技巧的理解和应用。