佛山专业建设网站平台,wordpress 备份 教程,网站运行团队建设,网站建设实习周记给定一个字符串 s#xff0c;找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1#xff1a;
输入: babad 输出: bab 注意: aba 也是一个有效答案。 示例 2#xff1a;
输入: cbbd 输出: bb找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1
输入: babad 输出: bab 注意: aba 也是一个有效答案。 示例 2
输入: cbbd 输出: bb 思路中心扩展法
每次都以一个点或者两个点为中心向两边扩散如果左右字符相等就继续遍历
以一个点为中心是因为回文字符串长度可能是奇数比如ababa
以两个点为中心是因为回文字符串长度可能是偶数比如ababab
代码
class Solution { public String longestPalindrome(String s) { if(s.length()0){ return s; } int start0,end0; for(int i0;is.length();i){ int ji helper(s,i,i); int ou helper(s,i,i1); int temp Math.max(ji,ou);//比较以一个点为中心和以两个点为中心的长度 if(tempend-start){ start i-(temp-1)/2; end itemp/2; } } return s.substring(start,end1); } public int helper(String s,int i,int j){ while(i0js.length()){ if(s.charAt(i)s.charAt(j)){ i--; j; }else{ break; } } return j-i-1; }
}
