2.24 Longest Palindrome Substring

Description

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.

Method

one : two pointers o(n^2) extend the two pointers from inner to outer to extend the palindrome as possible.

two: DP If a substring (i, j) is a panlindrome, then (i + 1, j - 1) is also a palindrome. So we can use this dependency to extend substring while avoid repeated comparsion // M[i][j] : represents the longest panlindrome from (0,0) to (i, j); // M[i][j] = true if (s.(i) == s(j) && m[i + 1][ j - 1]) // false else // result = Math.max(res, j - i + 1) // eg : // b b a b // b b a b // 0 1 2 3 // b 0 T T T F // b 1 T F T // a 2 T F // b 3 T

Time and Space Complexity

one : o(n^2) two : O(n), space : o(1)

Code

one : private int maxLen = 0; private int lo = 0;

 public String longestPalindrome(String s) {
      if (s == null || s.length() < 2){
          return s;
      }
      for (int i = 0; i < s.length(); i++){
          extend(s, i, i);
          extend(s, i, i + 1);
      }
      return s.substring(lo, lo + maxLen);
}

 private void extend(String s, int l, int k){
        while (l >= 0 && k < s.length() && s.charAt(l) == s.charAt(k)){
              l--;
              k++;
        }
        if (maxLen < k - l - 1){
            maxLen = k - l - 1;
            lo = l + 1;
        }
}

two:

public String longestPalindrome(String s){
       if (s == null || s.length() < 2){
           return s;
       }
       int len = s.length();
       boolean[][] isPalindrome = new boolean[len][len];

       String res = "";
       int maxLen = 0;

       for (int l = 0; l <= len - 1; l++){
            for (int i = 0; i < len - l; i++){
                 int j = i + l;

                 if (s.charAt(i) == s.charAt(j) && (j - i <= 2 || isPalindrome[i + 1][j - 1] == true)){
                     isPalindrome[i][j] = true;

                     if (j - i + 1 > maxLen){
                         maxLen = j - i + 1;
                         res = s.substring(i, j + 1);
                     }
                 }
            }
       }
       return res;

}