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, 
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.

class Solution { 
public: 
    /** 
     * @param s input string 
     * @return the longest palindromic substring 
     */ 
    string longestPalindrome(string& s) { 
        string result; 
        if (s.empty()) return s; 
 
        int n = s.size(); 
        int longest = 0, left = 0, right = 0; 
        for (int i = 0; i < n; ++i) { 
            for (int j = i + 1; j <= n; ++j) { 
                string substr = s.substr(i, j - i); 
                if (isPalindrome(substr) && substr.size() > longest) { 
                    longest = j - i; 
                    left = i; 
                    right = j; 
                } 
            } 
        } 
 
        result = s.substr(left, right - left); 
        return result; 
    } 
 
private: 
    bool isPalindrome(string &s) { 
        int n = s.size(); 
        for (int i = 0; i < n; ++i) { 
            if (s[i] != s[n - i - 1]) return false; 
        } 
        return true; 
    } 
};

public class Solution { 
    /** 
     * @param s input string 
     * @return the longest palindromic substring 
     */ 
    public String longestPalindrome(String s) { 
        String result = new String(); 
        if (s == null || s.isEmpty()) return result; 
 
        int n = s.length(); 
        int longest = 0, left = 0, right = 0; 
        for (int i = 0; i < n; i++) { 
            for (int j = i + 1; j <= n; j++) { 
                String substr = s.substring(i, j); 
                if (isPalindrome(substr) && substr.length() > longest) { 
                    longest = substr.length(); 
                    left = i; 
                    right = j; 
                } 
            } 
        } 
 
        result = s.substring(left, right); 
        return result; 
    } 
 
    private boolean isPalindrome(String s) { 
        if (s == null || s.isEmpty()) return false; 
 
        int n = s.length(); 
        for (int i = 0; i < n; i++) { 
            if (s.charAt(i) != s.charAt(n - i - 1)) return false; 
        } 
 
        return true; 
    } 
}