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.
所謂回文字元串，就是一個字元串，從左到右讀和從右到左讀是完全一樣的。比如”a” , “aaabbaaa”
之前去筆試了三星研究院，寫算法題的時候限定了程式設計語言隻能使用的頭檔案和庫函數，這在很大程度上考察了一個程式員的機關時間生産力。比如java隻能用util包，c/c++語言隻能包含以下三個頭檔案:
stdio.h
malloc.h //ANSI标準建議使用stdlib.h頭檔案
iostream.h // 非标準輸入輸出，不需要命名空間
是以我想，針對這種高标準的要求，以後做leetcode系列時應該寫三個版本，c語言版本不使用庫函數，c++版本使用STL，python版本
對于字元串的每一個子串，都判斷一下是不是回文字元串，完後傳回最長的那一個
(Brute Force) [Time Limit Exceeded]
時間複雜度分析：O（n3），空間複雜度O（n）,顯然逾時了。
Approach #1 (Longest Common Substring) [Accepted]
Common mistake
Some people will be tempted to come up with a quick solution, which is unfortunately flawed (however can be corrected easily):
Reverse S and become S′.
Find the longest common substring between S and S′, which must also be the longest palindromic substring.This seemed to work, let’s see some examples below.
For example,
S=”caba”
S′=”abac”
The longest common substring between S and S′ is ”aba”, which is the answer.
Let’s try another example:
S=”abacdfgdcaba”
S′=”abacdgfdcaba”
The longest common substring between S and S′ is ”abacd”
Clearly, this is not a valid palindrome.
To improve over the brute force solution, we first observe how we can avoid unnecessary re-computation while validating palindromes. Consider the case
”ababa”
”ababa”. If we already knew that
”bab”
”bab” is a palindrome, it is obvious that
”ababa” must be a palindrome since the two left and right end letters are the same.
We define P(i,j)P(i,j) as following:
P(i,j)={true,
if the substring Si…Sj is a palindrome
false,
otherwise.
P(i,j)={true,if the substring Si…Sj is a palindromefalse,otherwise.
Therefore,
P(i, j) = ( P(i+1, j-1) \text{ and } S_i == S_j ) P(i,j)=(P(i+1,j−1) and Si==Sj)
The base cases are:
P(i, i) = true P(i,i)=true
P(i, i+1) = ( S_i == S_{i+1} ) P(i,i+1)=(Si ==Si+1)
This yields a straight forward DP solution, which we first initialize the one and two letters palindromes, and work our way up finding all three letters palindromes, and so on…
Complexity Analysis
Time complexity : O(n^2)O(n2). This gives us a runtime complexity of O(n^2)O(n2).
Space complexity : O(n^2)O(n2). It uses O(n^2)O(n2) space to store the table.
Additional Exercise
Could you improve the above space complexity further and how?
In fact, we could solve it in O(n^2)O(n2 ) time using only constant space.
We observe that a palindrome mirrors around its center. Therefore, a palindrome can be expanded from its center, and there are only 2n - 12n−1 such centers.
You might be asking why there are 2n - 12n−1 but not nn centers? The reason is the center of a palindrome can be in between two letters. Such palindromes have even number of letters (such as
”abba””abba”) and its center are between the two ‘b”b’s.
public String longestPalindrome(String s) {
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
int len1 = expandAroundCenter(s, i, i);
int len2 = expandAroundCenter(s, i, i + 1);
int len = Math.max(len1, len2);
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
return s.substring(start, end + 1);
private int expandAroundCenter(String s, int left, int right) {
int L = left, R = right;
while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
L–;
R++;
return R - L - 1;
Time complexity : O(n^2)O(n2 ). Since expanding a palindrome around its center could take O(n)O(n) time, the overall complexity is O(n^2)O(n2 ).
Space complexity : O(1)O(1).
There is even an O(n)O(n) algorithm called Manacher’s algorithm, explained here in detail. However, it is a non-trivial algorithm, and no one expects you to come up with this algorithm in a 45 minutes coding session. But, please go ahead and understand it, I promise it will be a lot of fun.
c代碼
c++代碼
python參考代碼
<a href="http://articles.leetcode.com/longest-palindromic-substring-part-ii/">http://articles.leetcode.com/longest-palindromic-substring-part-ii/</a> <a href="https://www.felix021.com/blog/read.php?2040">https://www.felix021.com/blog/read.php?2040</a> <a href="https://leetcode.com/articles/longest-palindromic-substring/">https://leetcode.com/articles/longest-palindromic-substring/</a>
![mybatis_入門程式Mybatis入門[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)