Longest Palindromic Substring

Tags: String, Medium

Question

Problem Statement

Given a string s, find the longest palindromic substring in s. You may
assume that the maximum length of s is 1000.

Example:

  1. **Input:** "babad"
  3. **Output:** "bab"
  5. **Note:** "aba" is also a valid answer.

Example:

  1. **Input:** "cbbd"
  3. **Output:** "bb"

题解1 - 穷竭搜索

最简单的方案，穷举所有可能的子串，判断子串是否为回文，使用一变量记录最大回文长度，若新的回文超过之前的最大回文长度则更新标记变量并记录当前回文的起止索引，最后返回最长回文子串。

Python

  1. class Solution:
  2.     # @param {string} s input string
  3.     # @return {string} the longest palindromic substring
  4.     def longestPalindrome(self, s):
  5.         if not s:
  6.             return ""
  8.         n = len(s)
  9.         longest, left, right = 0, 0, 0
  10.         for i in xrange(0, n):
  11.             for j in xrange(i + 1, n + 1):
  12.                 substr = s[i:j]
  13.                 if self.isPalindrome(substr) and len(substr) > longest:
  14.                     longest = len(substr)
  15.                     left, right = i, j
  16.         # construct longest substr
  17.         result = s[left:right]
  18.         return result
  20.     def isPalindrome(self, s):
  21.         if not s:
  22.             return False
  23.         # reverse compare
  24.         return s == s[::-1]

C++

  1. class Solution {
  2. public:
  3.     /**
  4.      * @param s input string
  5.      * @return the longest palindromic substring
  6.      */
  7.     string longestPalindrome(string& s) {
  8.         string result;
  9.         if (s.empty()) return s;
  11.         int n = s.size();
  12.         int longest = 0, left = 0, right = 0;
  13.         for (int i = 0; i < n; ++i) {
  14.             for (int j = i + 1; j <= n; ++j) {
  15.                 string substr = s.substr(i, j - i);
  16.                 if (isPalindrome(substr) && substr.size() > longest) {
  17.                     longest = j - i;
  18.                     left = i;
  19.                     right = j;
  20.                 }
  21.             }
  22.         }
  24.         result = s.substr(left, right - left);
  25.         return result;
  26.     }
  28. private:
  29.     bool isPalindrome(string &s) {
  30.         int n = s.size();
  31.         for (int i = 0; i < n; ++i) {
  32.             if (s[i] != s[n - i - 1]) return false;
  33.         }
  34.         return true;
  35.     }
  36. };

Java

  1. public class Solution {
  2.     public String longestPalindrome(String s) {
  3.         if (s == null || s.isEmpty()) return "";
  5.         final int sLen = s.length();
  6.         int longest = 0, left = 0;
  7.         for (int i = 0; i < sLen; i++) {
  8.             for (int j = i; j < sLen; j++) {
  9.                 if (j - i + 1 > longest && isPalindrome(s, i, j)) {
  10.                     longest = j - i + 1;
  11.                     left = i;
  12.                 }
  13.             }
  14.         }
  16.         return s.substring(left, left + longest);
  17.     }
  19.     private boolean isPalindrome(String s, int left, int right) {
  20.         for (int i = left, j = right; i <= j; i++, j--) {
  21.             if (s.charAt(i) != s.charAt(j)) return false;
  22.         }
  23.         return true;
  24.     }
  25. }

源码分析

使用 left 作为子串的起止索引，longest 作为当前最长长度，用于最后构造返回结果，避免中间构造字符串以减少开销。两重循环中需要注意的是第二重循环的起止值及判断回文中的索引起止值。

复杂度分析

穷举所有的子串，O(C_n^2) = O(n^2), 每次判断字符串是否为回文，复杂度为 O(n), 故总的时间复杂度为 O(n^3), 大数据集下可能 TLE. 仅在最后返回取子串，空间复杂度为 O(1).
P.S. 目前仅 Java 对回文判断优化过。

题解2

题解1 中的思路是从子串出发判断回文串进而取最长，可以发现其中有许多重复的计算，如果我们从回文串本身出发进行求解，即从子串中间向左向右判断是否符合要求，由于回文串必定是某一子串，故只需从字符串的某一索引展开，分奇偶长度判断，时间复杂度可降为 O(n^2).

C++

  1. string palindrome(string& s, int l, int r) {
  2.     while (l>=0 && r<s.size() && s[l]==s[r]) l--, r++;
  3.     return s.substr(l+1, r-l-1);
  4. }
  6. string longestPalindrome(string s) {
  7.     if (s.empty()) return s;
  9.     string res;
  10.     for (int i=0; i<s.size(); i++) {
  11.         string t;
  12.         t = palindrome(s, i, i);
  13.         if (t.size() > res.size()) res = t;
  15.         t = palindrome(s, i, i+1);
  16.         if (t.size() > res.size()) res = t;   
  17.     }
  18.     return res;
  19. }

Java

  1. public class Solution {
  2.     public String longestPalindrome(String s) {
  3.         if (s == null || s.isEmpty()) return "";
  5.         final int sLen = s.length();
  6.         int longest = 0, left = 0;
  7.         for (int i = 0; i < sLen; i++) {
  8.             // odd
  9.             int leftIndex = leftPalindromeIndex(s, i, i);
  10.             int palindromeLen = 2 * (i - leftIndex) + 1;
  11.             if (palindromeLen > longest) {
  12.                 left = leftIndex;
  13.                 longest = palindromeLen;
  14.             }
  15.             // even
  16.             leftIndex = leftPalindromeIndex(s, i, i + 1);
  17.             palindromeLen = 2 * (i - leftIndex + 1);
  18.             if (palindromeLen > longest) {
  19.                 left = leftIndex;
  20.                 longest = palindromeLen;
  21.             }
  22.         }
  24.         return s.substring(left, left + longest);
  25.     }
  27.     private int leftPalindromeIndex(String s, int left, int right) {
  28.         for (; left >= 0 && right < s.length(); left--, right++) {
  29.             if (s.charAt(left) != s.charAt(right)) break;
  30.         }
  31.         return left + 1;
  32.     }
  33. }

源码分析

假定扫描的每个字母是回文的中间位置（需要处理奇偶两种情况），从该位置向两头搜索寻找最大回文长度。

复杂度分析

时间复杂度降到 O(n^2).

题解3

另外还有一个O（n）的解法，具体参考下面的链接
http://articles.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html

Reference