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.

    Example:

    3. **Output:** "bb"

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

    Python

    C++

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

    源码分析

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

    复杂度分析

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

    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;

    Java

    源码分析

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

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