leetcode-5.最长回文子串
36 浏览量
2020-12-21
01:49:32
上传
评论
收藏 41KB PDF 举报
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的位置的字符串是否是回文子串
boolean[][]nums=new boolean[s.length()][s.length()];
//left表示记录下的回文字符串的开始位置
int left=0;
//length用于保存回文串的长度
int length=1;
for(int i=0;i<s.length();i++){
for(int j=0;j<=i;j++){
//如果s.charAt(j)==s.charAt(i)
//比如对于babad
//假设当前j=0；i=2，两个位置都为b，如果不等直接进行下一次循环
//如果两个位置字符相等，需要判断i-j的大小
//比如bb或者bab或者bacb
//对于前两种可以直接进行判断，第三种需要判断j+1到i-1的字符是否为回文子串
if(s.charAt(j)==s.charAt(i)&&(i-jlength){
left=j;
length=i-j+1;
}
}
}
}
return s.substring(left,left+length);
}
代码二代码二
class Solution {
private int length=1;
private int index=0;
public String longestPalindrome(String s) {
if(s.length()==0||s.length()==1){return s;}
for(int i=0;i=0&&rightlength){
length=right-left+1;index=left;
}
left--;
right++;
}
}
}
今天会是有offfer的一天么
原创文章 24获赞 53访问量 4万+
关注
私信
评论0