一、题目

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.

Example

Given the string = "abcdzdcab", return "cdzdc".

Challenge

O(n2) time is acceptable. Can you do it in O(n) time.

求一个字符串中的最长回文子串。

二、解题思路

区间类动态规划

Time O(n^2), Space O(n^2)

用dp[i][j]来存DP的状态，需要较多的额外空间: Space O(n^2)

DP的4个要素

  • 状态：
    • dp[i][j]: s.charAt(i)到s.charAt(j)是否构成一个Palindrome
  • 转移方程：
    • dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])
  • 初始化：
    • dp[i][j] = true when j - i <= 2
  • 结果：
    • 找 maxLen = j - i + 1;，并得到相应longest substring： longest = s.substring(i, j + 1);

中心扩展

这种方法基本思想是遍历数组，以其中的1个元素或者2个元素作为palindrome的中心，通过辅助函数，寻找能拓展得到的最长子字符串。外层循环 O(n)，内层循环O(n)，因此时间复杂度 Time O(n^2)，相比动态规划二维数组存状态的方法，因为只需要存最长palindrome子字符串本身，这里空间更优化：Space O(1)。

三、解题代码

区间DP，Time O(n^2) Space O(n^2)

  1. public class Solution {
  2.     /**
  3.      * @param s input string
  4.      * @return the longest palindromic substring
  5.      */
  6.      public String longestPalindrome(String s) {
  7.          if(s == null || s.length() <= 1) {
  8.              return s;
  9.          }
  11.          int len = s.length();
  12.          int maxLen = 1;
  13.          boolean [][] dp = new boolean[len][len];
  15.          String longest = null;
  16.          for(int k = 0; k < s.length(); k++){
  17.              for(int i = 0; i < len - k; i++){
  18.                  int j = i + k;
  19.                  if(s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])){
  20.                      dp[i][j] = true;
  22.                      if(j - i + 1 > maxLen){
  23.                         maxLen = j - i + 1;
  24.                         longest = s.substring(i, j + 1);
  25.                      }
  26.                  }
  27.              }
  28.          }
  30.          return longest;
  31.      }
  32. }

Time O(n^2) Space O(1)

  1. public class Solution {
  2.     /**
  3.      * @param s input string
  4.      * @return the longest palindromic substring
  5.      */
  6.     public String longestPalindrome(String s) {
  7.             if (s.isEmpty()) {
  8.                 return null;
  9.             }
  11.             if (s.length() == 1) {
  12.                 return s;
  13.             }
  15.             String longest = s.substring(0, 1);
  16.             for (int i = 0; i < s.length(); i++) {
  17.                 // get longest palindrome with center of i
  18.                 String tmp = helper(s, i, i);
  19.                 if (tmp.length() > longest.length()) {
  20.                     longest = tmp;
  21.                 }
  23.                 // get longest palindrome with center of i, i+1
  24.                 tmp = helper(s, i, i + 1);
  25.                 if (tmp.length() > longest.length()) {
  26.                     longest = tmp;
  27.                 }
  28.             }
  30.             return longest;
  31.     }
  33.     // Given a center, either one letter or two letter,
  34.     // Find longest palindrome
  35.     public String helper(String s, int begin, int end) {
  36.         while (begin >= 0 && end <= s.length() - 1 && s.charAt(begin) == s.charAt(end)) {
  37.             begin--;
  38.             end++;
  39.         }
  40.         return s.substring(begin + 1, end);
  41.     }
  42. }