最长回文字符串题解(动态规划)

LeetCode正题Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.ExampleInput: "babad"Output: "bab"Note: "aba" is also a valid answer.ExampleInput: "cbbd"Output: "bb"思考回文字符串即正向顺序和反向顺序的字幕排序是一致的字段串。题的大意为寻找一个指定字符串中的最长的回文字符串。首选,暴力解法需要遍历所有子串并判断子串是否为回文字符串。假设给定字符串长度n,那么子串的总数为​n(n+1)/2(即1 2 3 ... n的和),即需要O(n^2),然后判断每个子串是否为回文字符串的时间复杂度为O(n),即总共需要... Read More