<feat> add problem 5

bluedazzle · bluedazzle · commit 72ced9ab827f · 2016-10-31T22:57:47.000+08:00
Author:rapospectre@gmail.com

Desc: add problem Longest Palindromic Substring
diff --git a/readme.md b/readme.md
@@ -6,6 +6,9 @@
 #### 2. [Add Two Numbers][3]: [Solution][4]
 #### 3. [Longest Substring Without Repeating Characters][5]: [Solution][6]
 #### 4. [Median of Two Sorted Arrays][7]: [Solution][8]
+#### 5. [Longest Palindromic Substring][9]: [Solution][10]
+(&#36825;&#36947;&#39064;&#23545; Python &#26377;&#27602;, &#21482;&#35201;&#26102;&#38388;&#22797;&#26434;&#24230;&#22823;&#20110;&#31561;&#20110; O(n2) &#32477;&#23545; TLE, &#20854;&#23427;&#35821;&#35328; O(n3) &#20063;&#33021;&#36807;...) 
+##### tips: Python &#29992; Manacher&rsquo;s Algorithm &#27604;&#36739;&#31283;, &#20854;&#23427;&#31639;&#27861;&#22522;&#26412; TLE. &#26412;&#20363;&#37324;&#29992;&#23558;&#27599;&#20010;&#23383;&#31526;&#24403;&#20316;&#22238;&#25991;&#20018;&#20013;&#24515;&#23545;&#21305;&#37197;&#26041;&#24335;,&#36824;&#26159;&#21487;&#33021; TLE.
 
 
 [1]: https://leetcode.com/problems/two-sum/
@@ -15,4 +18,6 @@
 [5]: https://leetcode.com/problems/longest-substring-without-repeating-characters/
 [6]: https://github.com/bluedazzle/leetcode_python/blob/master/src/lswrc.py
 [7]: https://leetcode.com/problems/median-of-two-sorted-arrays
-[8]: https://github.com/bluedazzle/leetcode_python/blob/master/src/motsa.py
+[8]: https://github.com/bluedazzle/leetcode_python/blob/master/src/motsa.py
+[9]: https://leetcode.com/problems/longest-palindromic-substring/
+[10]: https://github.com/bluedazzle/leetcode_python/blob/master/src/longest_palindromic_substring.py
diff --git a/src/longest_palindromic_substring.py b/src/longest_palindromic_substring.py
@@ -0,0 +1,45 @@
+# coding: utf-8
+
+# author: RaPoSpectre
+# time: 2016-10-31
+
+
+# &#23558;&#27599;&#20010;&#23383;&#31526;&#20018;&#24403;&#20316;&#22238;&#25991;&#20018;&#30340;&#20013;&#24515;&#36827;&#34892;&#39564;&#35777;
+
+class Solution(object):
+    def find_from_center(self, s, ms, cs):
+        jts = ''
+        ots = ''
+        j = True
+        o = True
+        for i in xrange(0, ms + 1):
+            if s[cs - i] == s[cs + i] and j:
+                jts = s[cs - i: cs + i + 1]
+            else:
+                j = False
+            if ms + cs + 1 == len(s) and i == ms:
+                break
+            if s[cs - i] == s[cs + i + 1] and o:
+                ots = s[cs - i: cs + i + 2]
+            else:
+                o = False
+        if len(ots) > len(jts):
+            return ots
+        return jts
+
+    def longestPalindrome(self, s):
+        """
+        :type s: str
+        :rtype: str
+        """
+        rs = ''
+        for i in xrange(0, len(s)):
+            ts = i
+            te = len(s) - i - 1
+            if ts < te:
+                tmp = self.find_from_center(s, ts, i)
+            else:
+                tmp = self.find_from_center(s, te, i)
+            if len(tmp) > len(rs):
+                rs = tmp
+        return rs
diff --git a/src/sunday.py b/src/sunday.py
@@ -0,0 +1,36 @@
+# coding: utf-8
+
+# author: RaPoSpectre
+# time: 2016-10-31
+
+
+def sunday(s, model):
+    match = False
+    ms = 0
+    me = len(model)
+
+    if s == model:
+        print '&#21305;&#37197;&#25104;&#21151;,&#20301;&#32622;: s[{0}]->s[{1}]'.format(0, len(model))
+        return True
+
+    while 1:
+        p = s[ms: me]
+        if model == p:
+            match = True
+            print '&#21305;&#37197;&#25104;&#21151;,&#20301;&#32622;: s[{0}]->s[{1}]'.format(ms, me)
+            break
+        if me >= len(s):
+            break
+        sign = s[me]
+        if sign in model:
+            posi = model.rfind(sign)
+            offset = len(model) - posi
+            ms += offset
+            me += offset
+        else:
+            ms += len(model)
+            me += len(model)
+    return match
+
+
+# print sunday('abxdcsxxefre', 'xx')
