CML00
diff --git a/‎String/Medium/5.Longest Palindromic Substring.md
Lines changed: 95 additions & 0 deletions b/‎String/Medium/5.Longest Palindromic Substring.md
Lines changed: 95 additions & 0 deletions
@@ -0,0 +1,95 @@
+# 题目
+给定一个字符串s，找到最长回文子字符串s。假设s的最大长度为s。
+
+**举例1：**
+
+``` 
+输入："babad"
+输出："bab"
+注意："aba"也是一个有效结果。
+```
+
+**举例2：**
+
+``` 
+输入："cbbd"
+输出："bb"
+```
+
+# 思路
+
+可以使用中心扩展的方法，把给定的每一个字母当做中心，向两边扩展，这样找到最长的子回文串。算法复杂度为O(N^2)。
+分为两种情况：
+
+ - aba，这样长度为奇数的回文
+ - abba，这样长度为偶数的回文
+
+# 代码
+基本方法：
+
+``` python
+class Solution(object):
+    def longestPalindrome(self, s):
+        """
+        :type s: str
+        :rtype: str
+        """
+        length = len(s)
+        maxlength = 1
+        start = 0
+        if length == 0: return None
+        if length == 1: return True
+
+        #奇数回文
+        for i in range(length):		
+            j = i - 1
+            k = i + 1
+            while j >= 0 and k < length and s[j] == s[k]:
+                if k - j + 1 > maxlength:
+                    maxlength = k - j + 1
+                    start = j
+                j -= 1
+                k += 1
+
+        #偶数回文
+        for i in range(length):
+            j = i
+            k = i + 1
+            while j >= 0 and k < length and s[j] == s[k]:
+                if k - j + 1 > maxlength:
+                    maxlength = k - j + 1
+                    start = j 
+                j -= 1
+                k += 1
+
+        if maxlength > 0:
+            return s[start:start+maxlength]
+        return None
+```
+
+改进方法：
+
+``` python
+class Solution(object):
+    def longestPalindrome(self, s):
+        """
+        :type s: str
+        :rtype: str
+        """
+        if len(s)==0:
+            return 0
+        maxLen=1
+        start=0
+        for i in range(len(s)):
+            if i-maxLen >=1 and s[i-maxLen-1:i+1]==s[i-maxLen-1:i+1][::-1]:
+                start=i-maxLen-1
+                maxLen+=2
+                continue
+
+            if i-maxLen >=0 and s[i-maxLen:i+1]==s[i-maxLen:i+1][::-1]:
+                start=i-maxLen
+                maxLen+=1
+        return s[start:start+maxLen]
+```
+
+