leetcode答案-2020.9.18:2020.9.18

leetcode 答案 2020.9.18————最长回文子串 题目 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例 1： 输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。 示例 2： 输入: "cbbd" 输出: "bb" 解题 语言 java 思路 对于一个子串而言，如果它是回文串，并且长度大于 22，那么将它首尾的两个字母去除之后，它仍然是个回文串。例如对于字符串 “ababa”，如果我们已经知道 “bab” 是回文串，那么 “ababa” 一定是回文串，这是因为它的首尾两个字母都是“a”。 根据这样的思路，我们就可以用动态规划的方法解决本题。我们用 P(i,j)P(i,j) 表示字符串 ss 的第 ii 到 jj 个字母组成的串（下文表示成 s[i:j]s[i:j]）是否为回文串： 这里的「其它情况」包含两种可能性： s[i, j]s[i,j] 本身不是一个回文串； i > ji>j，此时 s[i, j]s[i,j] 本身不合法。 那么我们就可以写出动态规划的状态转移方程： 也就是说，只有 s[i