|
| 1 | +#!/usr/bin/env python |
| 2 | +# -*- coding:UTF-8 |
| 3 | +__author__='shenshijun' |
| 4 | +""" |
| 5 | +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. |
| 6 | +
|
| 7 | +我的解法就是这个解法：http://taop.marchtea.com/01.05.html |
| 8 | +感谢 |
| 9 | +""" |
| 10 | + |
| 11 | + |
| 12 | +classSolution(object): |
| 13 | +deflongestPalindrome(self,original): |
| 14 | +""" |
| 15 | + :type s: str |
| 16 | + :rtype: str |
| 17 | + """ |
| 18 | +ifnotoriginal: |
| 19 | +return0 |
| 20 | +s=self.__preProcess(original) |
| 21 | +longest_right_bound=0 |
| 22 | +longest_median=0 |
| 23 | +pali_list= [1foriinrange(len(s))] |
| 24 | +# 注意迭代位置，为了不出现越界，最前和最后的字符串是不会被遍历的 |
| 25 | +foriinrange(1,len(s)-1): |
| 26 | +# 这边使用的是对称的原理，使得可以快速个p[i]一个基础的值 |
| 27 | +iflongest_right_bound>i: |
| 28 | +iflongest_right_bound-i<=pali_list[2*longest_median-i]: |
| 29 | +pali_list[i]=longest_right_bound-i |
| 30 | +else: |
| 31 | +pali_list[i]=pali_list[2*longest_median-i] |
| 32 | +# 在字符串的最前面和最后面都必须加上一个特殊字符，用于防止越界 |
| 33 | +# 另一个方法是在每次循环的时候都判断边界，但是效率比直接加特殊字符低 |
| 34 | +whiles[i+pali_list[i]]==s[i-pali_list[i]]: |
| 35 | +pali_list[i]+=1 |
| 36 | +ifpali_list[i]>=longest_right_bound-longest_median: |
| 37 | +longest_right_bound=pali_list[i]+i |
| 38 | +longest_median=i |
| 39 | +returnself.__clearString(s[2*longest_median-longest_right_bound+1:longest_right_bound]) |
| 40 | + |
| 41 | +def__clearString(self,sub_str): |
| 42 | +return"".join([chforchinsub_strifch!='#']) |
| 43 | + |
| 44 | +def__preProcess(self,s): |
| 45 | +str_list= ['#{}'.format(ele)foreleins] |
| 46 | +str_list.append("#$") |
| 47 | +str_list.insert(0,'^') |
| 48 | +return"".join(str_list) |
| 49 | + |
| 50 | + |
| 51 | +defmain(): |
| 52 | +print(Solution().longestPalindrome("bbbbbb"))# 6 |
| 53 | +print(Solution().longestPalindrome("fqwefqwefqwadccdaafwfawef"))# 6 |
| 54 | +print(Solution().longestPalindrome("qwefqwefqsjsjsssgsssjsjsg3q4gekwSKDFKALJKFIUWIUEFWEG"))# 15 |
| 55 | +print(Solution().longestPalindrome("ababababa"))# 10 |
| 56 | + |
| 57 | + |
| 58 | +if__name__=="__main__": |
| 59 | +main() |
