最长回文子串是hihocoder上的一道练习题,hihocoder只支持C、C++、Java,不支持Python。目前在学Python,看到这个题恰好能做就做了一下。Leetcode是支持python的,以后可以在leetcode上练练。
小Hi和小Ho是一对好朋友,出生在信息化社会的他们对编程产生了莫大的兴趣,他们约定好互相帮助,在编程的学习道路上一同前进。
这一天,他们遇到了一连串的字符串,于是小Hi就向小Ho提出了那个经典的问题:“小Ho,你能不能分别在这些字符串中找到它们每一个的最长回文子串呢?”
小Ho奇怪的问道:“什么叫做最长回文子串呢?”
小Hi回答道:“一个字符串中连续的一段就是这个字符串的子串,而回文串指的是12421这种从前往后读和从后往前读一模一样的字符串,所以最长回文子串的意思就是这个字符串中最长的身为回文串的子串啦~”
小Ho道:“原来如此!那么我该怎么得到这些字符串呢?我又应该怎么告诉你我所计算出的最长回文子串呢?
小Hi笑着说道:“这个很容易啦,你只需要写一个程序,先从标准输入读取一个整数N(N<=30),代表我给你的字符串的个数,然后接下来的就是我要给你的那N个字符串(字符串长度<=10^6)啦。而你要告诉我你的答案的话,只要将你计算出的最长回文子串的长度按照我给你的顺序依次输出到标准输出就可以了!你看这就是一个例子。” 样例输入
3 abababa aaaabaa acacdas样例输出7 5 3我是这么想的,把一个字符串和字符串的子串都检查一边,是回文的话就把子串的长度和子串作为一个turple储存在一个list里面。然后list降序排列,第一个结果就是最大回文了。def check_huiwen(s): return s == s[::-1]
def max_huiwen(s): n = len(s) new_list = list() for i in range(1, n+1): for j in range(n-i+1): huiwen = s[j:j+i] if check_huiwen(huiwen): new_list.append((len(huiwen),huiwen))
new_list.sort(reverse=True)
print new_list[0][0]
判断一个字符串是不是回文很简单,直接判断它和它逆序的list的值是否相同即可。 找最大回文子串的时候,第一个循环控制子串的长度,第二个按起始位置循环遍历每一个子串,是回文的就存储起来,然后排序,最后输出。 这是《Think Python》里介绍的典型的DSU模式:
- 修饰(Decorate):构建一个元组列表,在序列元素之前放置一个或多个排序键。
- 排序(Sort):给这个序列排序,并。
- 去修饰(Undecorate):抽取排好序的序列中的元素。 补充资料:http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html
未完待续。
2015-01-08