Update shortest-palindrome.py

kamyu104 · kamyu104 · commit 66c36c8d7a66 · 2016-03-13T11:31:25.000+08:00
diff --git a/Python/shortest-palindrome.py b/Python/shortest-palindrome.py
@@ -19,26 +19,26 @@ def shortestPalindrome(self, s):
         :type s: str
         :rtype: str
         """
+        def getPrefix(pattern):
+            prefix = [-1] * len(pattern)
+            j = -1
+            for i in xrange(1, len(pattern)):
+                while j > -1 and pattern[j+1] != pattern[i]:
+                    j = prefix[j]
+                if pattern[j+1] == pattern[i]:
+                    j += 1
+                prefix[i] = j
+            return prefix
+
         if not s:
             return s
             
         A = s + s[::-1]
-        prefix = self.getPrefix(A)
+        prefix = getPrefix(A)
         i = prefix[-1]
         while i >= len(s):
             i = prefix[i]
         return s[i+1:][::-1] + s
-        
-    def getPrefix(self, pattern):
-        prefix = [-1] * len(pattern)
-        j = -1
-        for i in xrange(1, len(pattern)):
-            while j > -1 and pattern[j+1] != pattern[i]:
-                j = prefix[j]
-            if pattern[j+1] == pattern[i]:
-                j += 1
-            prefix[i] = j
-        return prefix
 
 
 # Time:  O(n)
