欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

5. Longest Palindromic Substring

程序员文章站 2024-03-23 11:36:22
...

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.


// 思路: 从中间向两边扩展。分两个case : (i, i) 和(i, i+1) 
// Time O(n^2), Space O(1)
//http://www.programcreek.com/2013/12/leetcode-solution-of-longest-palindromic-substring-java/
 public String longestPalindrome(String s) {
  String longest = s.substring(0,1); 
  if (s.isEmpty()) {
   return null;
  }
  if (s.length() == 1) return s;
  
  for (int i = 0; i < s.length(); i++) {
   // get longest palindomr with center of i, i ,  abcba
   String tmp = helper(s, i, i);
   if (tmp.length() > longest.length()) {
    longest = tmp;
   }
   // get longest palindomr with center of i, i+1  abba
   tmp = helper(s, i, i + 1);
   if (tmp.length() > longest.length()) {
    longest = tmp;
   }
  }
  return longest;
    }
  
 public String helper(String s, int start, int end) {
  while (start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)) {
   start--;
   end++;
  }
  return s.substring(start + 1, end);
 } 
**