首页 > 代码库 > Longest Palindromic Substring
Longest Palindromic Substring
Longest Palindromic Substring
Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
思路：
最开始想把所有子串都穷举出来，感觉不太靠谱。后面在纸上画了一下，想到一种方法
遍历整个字符串i
1.如果s.charAt(i) == s.charAt(i + 1)，以i和i+1为中心向两边扩展，如果是回文且长度超过了已经求得最长回文result，更新result
2.如果s.charAt(i - 1) == s.charAt(i + 1)，以i - 1和i + 1为中心向两边扩展，如果是回文且长度超过了已经求得的回文result，更新result
遍历结束返回result
1 public class Solution { 2 public String longestPalindrome(String s) { 3 if(0 == s.length() || 1 == s.length()) 4 return s; 5 else{ 6 String result = ""; 7 8 for(int i = 0; i < s.length(); i++){ 9 if(i + 1 < s.length() && s.charAt(i) == s.charAt(i + 1)){ //以i和i + 1为中心10 int j = i + 1;11 int k = i;12 // i = i;13 while(k >= 0 && j < s.length()){ //向中心两边扩展14 if(s.charAt(k) == s.charAt(j)){ 15 if((j - k + 1) > result.length()) //只有更大才能更新16 result = s.substring(k, j + 1); //开始索引包括，结束索引不包括 更新最长回文17 k--;18 j++;19 continue;20 }21 break; //两边不满足直接退出22 }23 }//if24 if(i - 1 >= 0 && i + 1 < s.length() && s.charAt(i - 1) == s.charAt(i + 1)){ //以i为中心25 int j = i + 1;26 int k = i - 1;27 // i = i - 1; //向中心两边扩展28 while(k >= 0 && j < s.length()){29 if(s.charAt(k) == s.charAt(j)){30 if((j - k + 1) > result.length())31 result = s.substring(k, j + 1);32 k--;33 j++;34 continue;35 }//while36 break;37 }38 }39 }40 41 return result;42 }43 }44 }
Longest Palindromic Substring
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。