亲宝软件园·资讯

展开

最长回文子串

LeeBoom 人气:0

对于一个子串而言,如果它是回文串,并且长度大于 2,那么将它首尾的两个相同的字母去除之后,它仍然是个回文串。所以状态转移方程为dp[i][j] = (dp[i+1][j-1]) && chars[i]==chars[j];同时对于j-1>=i+1 所以 j-i+1(数组长度)>=3,l=j-1>=2。
那么当l=0时,为字符本身,肯定为回文串。
当l=1时需要判断左右字符是否相等
这里使用位移量l作为循环变量,是为了防止出现dp[i][j]中j<i这种不合理的情况发生。所以使用j=i+l来代替 forj。第二个循环里使用i来代表下标,从0开始往后遍历,需要注意的是,由于j=i+l,而j的下标也是一定小于数组长度的,所以i+l<length;

//给你一个字符串 s,找到 s 中最长的回文子串。 
//
// 
//
// 示例 1: 
//
// 
//输入:s = "babad"
//输出:"bab"
//解释:"aba" 同样是符合题意的答案。
// 
//
// 示例 2: 
//
// 
//输入:s = "cbbd"
//输出:"bb"
// 
//
// 示例 3: 
//
// 
//输入:s = "a"
//输出:"a"
// 
//
// 示例 4: 
//
// 
//输入:s = "ac"
//输出:"a"
// 
//
// 
//
// 提示: 
//
// 
// 1 <= s.length <= 1000 
// s 仅由数字和英文字母(大写和/或小写)组成 
// 
// Related Topics 字符串 动态规划 
// 

加载全部内容

相关教程
猜你喜欢
用户评论